首页 > 代码库 > hoj 13788 Dwarves
hoj 13788 Dwarves
//首先判环我都不会 dfs实在写的戳 后来测了好多数据发现dfs写错了 唉 其次不会哈希啊 这个哈希还是dalao手写给我的 珍惜!!!
#include <iostream> #include <algorithm> #include <stdio.h> #include <vector> #include <string> #include <string.h> #include <queue> #include <math.h> #include <map> #define ULL unsigned long long using namespace std; const int maxn=10010; const int INF=0x3f3f3f3f; #define mod 10007 int cnt; vector <int> e[10010]; //map<ULL,int> mp; int f[10010]; int de[maxn]; int tot; bool flag=true; void dfs(int now){ f[now]=-1; for(int i=0;i<e[now].size();i++) { if(f[e[now][i]]==-1) {flag=false;} else if(f[e[now][i]]==0) dfs(e[now][i]); } f[now]=1; } const int maxbuf = 11111; struct node { ULL key; int id,next; }buf[maxbuf]; int h[maxn]; ULL fuck(char a[30]){ ULL ha=0; for(int i=0;a[i];i++){ ha*=52; ha+=a[i]; } return (ha); } void inithash() { tot = 0; memset(h,-1,sizeof(h)); } int ins(ULL key) { int now = ++tot; buf[now].key = key, buf[now].id = now, buf[now].next = h[key%mod]; h[key%mod] = now; return now; } int fnd(ULL key) { for (int i=h[key%mod];~i;i=buf[i].next) { if (buf[i].key == key) return buf[i].id; } return 0; } char s1[30],s2[30]; int main(){ #ifdef shuaishuai freopen("C:\\Users\\hasee\\Desktop\\trianglen=100000.in","r",stdin); // freopen("C:\\Users\\hasee\\Desktop\\b.txt","w",stdout); // freopen("C:\\Users\\hasee\\Desktop\\picture.in","r",stdin); #endif // ios::sync_with_stdio(false); char s; int n; memset(f,0,sizeof f); memset(de,0,sizeof de); inithash(); while(scanf("%d\n",&n)!=EOF) { cnt=1; for(int i=0;i<n;i++) { // cout<<"@"<<endl; scanf("%s %c %s\n",s1,&s,s2); // cout<<s1<<" "<<s<<" "<<s2<<endl; ULL x1=fuck(s1); ULL x2=fuck(s2); int u = fnd(x1), v = fnd(x2); // cout<<"before "<<u<<" "<<v<<" "<<tot<<endl; // cout<<x1<<" "<<x2<<endl; if (!u) u = ins(x1); if (!v) v = ins(x2); // printf("%s %d %s %d\n",s1,u,s2,v); // cout<<u<<" "<<v<<" "<<tot<<endl; // printf("%d %d\n",x1,x2); // int x1=mp[t1],x2=mp[t2]; // if(x1==0)x1=mp[t1]=cnt++; // if(x2==0)x2=mp[t2]=cnt++; if(s==‘>‘) { e[u].push_back(v); de[v]++; } else { e[v].push_back(u); de[u]++; } } for(int i=1;i<=tot;i++ ){ if(f[i]==0) dfs(i); if(!flag) break; } if(flag) printf("possible\n"); else printf("impossible\n"); for(int i=0;i<=tot;i++)e[i].clear(),f[i]=0,h[i]=-1,de[i]=0; tot=0; } return 0; }
hoj 13788 Dwarves
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。