hdu3234 Exclusive-OR 带权并查集

不想再调这道题了。。。这题我早就会了，但是读入实在是坑。。。。就是坑。。。。没错，这次真的是坑。。。。。。

不能在坑题上浪费太多时间，既没有明显提高代码能力，又不能提高思维，也不能学到知识点。

我只能说，出题人心理为何如此阴暗，出这样的题和报复社会有什么区别。。。

#include
#include
#include
#include
#include
#include
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))using namespace std;typedef long long ll;
const int maxn=1000100;
const int INF=1e9+10;int n,m;
char op[10];int p,q,v;
int k,pk[40];
vector<int> d[40];int dn;
int fa[maxn],w[maxn],val[maxn];
int flag;
int rk;
int sz[maxn];void Init()
{REP(i,0,2) fa[i]=i,w[i]=0,val[i]=-1,sz[i]=1;REP(i,0,20) d[i].clear();
}int find(int x)
{if(fa[x]==x) return x;int t=find(fa[x]);w[t]=0;w[x]^=w[fa[x]];return fa[x]=t;
}void Union(int p,int q,int v)
{if(flag==0) return;int x=find(p),y=find(q);if(x==y){if((w[p]^w[q])!=v) flag=0;}else{if(sz[x]>sz[y]) swap(x,y),swap(p,q);if(~val[x]&&~val[y]){if((w[p]^val[x]^w[q]^val[y])!=v) flag=0;else{fa[x]=y;sz[y]+=sz[x];sz[x]=0;w[x]=(w[p]^w[q]^v);w[y]=0;}}else{fa[x]=y;w[x]=(w[p]^w[q]^v);w[y]=0;if(val[y]==-1){if(~val[x]) val[y]=(val[x]^w[x]);}}}if(flag==0) printf("The first %d facts are conflicting.\n",rk);
}void change(int p,int v)
{if(flag==0) return;int x=find(p);if(~val[x]){if((w[p]^val[x])!=v) flag=0;}else val[x]=(v^w[p]);if(flag==0) printf("The first %d facts are conflicting.\n",rk);
}bool cmp(int a,int b)
{return fa[a]<fa[b];
}int query()
{REP(i,1,k) d[i].clear();int res=0;sort(pk+1,pk+k+1,cmp);dn=1;d[1].push_back(pk[1]);int px=fa[pk[1]];REP(i,2,k){if(fa[pk[i]]==px) d[dn].push_back(pk[i]);else{++dn;px=fa[pk[i]];d[dn].push_back(pk[i]);}}REP(i,1,dn){if((int)d[i].size()%2==0){for(int j=0;jw[d[i][j]];}else{int x=fa[d[i][0]];if(val[x]==-1) return -1;for(int j=0;jw[d[i][j]]);}}return res;
}void solve()
{flag=1;rk=0;REP(i,1,m){scanf("%s",op);if(op[0]=='I'){++rk;gets(op);if(sscanf(op,"%d%d%d",&p,&q,&v)==3) Union(p,q,v);else change(p,q);}else{scanf("%d",&k);REP(i,1,k){scanf("%d",&pk[i]);find(pk[i]);}if(flag==0) continue;ll tmp=query();if(tmp==-1) printf("I don't know.\n");else printf("%d\n",tmp);}}
}int main()
{freopen("in.txt","r",stdin);int casen=1;while(~scanf("%d%d",&n,&m)){if(n==0&&m==0) break;printf("Case %d:\n",casen++);Init();solve();puts("");}return 0;
}/**
6 5
I 1 2 1
I 3 4 2
I 4 5 3
Q 2 3 5
Q 4 1 2 3 5
2 6
I 0 1 3
Q 1 0
Q 2 1 0
I 0 2
Q 1 1
Q 1 0
3 3
I 0 1 6
I 0 2 2
Q 2 1 2
2 4
I 0 1 7
Q 2 0 1
I 0 1 8
Q 2 0 1
0 0
*/

转载于:https://www.cnblogs.com/--560/p/5274259.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！