HDU 3038（带权值并查集）
题意：给出m组区间[a,b]，以及其区间的和，问有矛盾的有几组；
做法：
sum[x]是x到根这段路径上的和
，那么根一定是坐标越小的，那么如果说对于同类（同一个集合）的判断就是sum[b]-sum[a-1]是否等于给出值。
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int pre[200010];
int sum[200010];
int f(int x)
{
if(x==pre[x]) return x;
int fx=pre[x];
pre[x]=f(pre[x]);
sum[x]+=sum[fx];
return pre[x];
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{ for(int i=0;i<=n;++i)
{
pre[i]=i; sum[i]=0;
}
int ans=0;
while(m--)
{
int x,y,val;
scanf("%d%d%d",&x,&y,&val); x--;
int fx=f(x),fy=f(y);
if(fx==fy&&sum[y]-sum[x]!=val)
{
ans++; continue;
}
else if(fx!=fy)
{
pre[fy]=fx;
sum[fy]=sum[x]+val-sum[y];
}
}
printf("%d\n",ans);
}
return 0;
}
POJ 1733
题意：一个由0,1组成的数字串~~，现在你问一个人，第i位到第j位的1的个数为奇数还是偶数。一共会告诉你几组这样的数要你判断前k组这个人回答的都是正确的，到第k+1组，这个人说的是错的，要你输出这个k，要是这个人回答的都是正确的，则输出组数
做法：带权并查集，sum[x]为x到fx之间的奇偶性，画个向量图就可以得到合并的sum操作（注意map离散化）
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
int pre[10010],sum[10010];
int n,m;
map<int,int> mp;
char s[10];
int f(int x)
{
if(x==pre[x]) return x;
int t=f(pre[x]);
sum[x]=(sum[x]+sum[pre[x]])%2;
return pre[x]=t;
}
int judge(int x,int y,int z)
{
int fx=f(x),fy=f(y);
if(fx==fy)
{
if((sum[x]+sum[y]+z)%2) return 0;
return 1;
}
pre[fy]=fx;
sum[fy]=(sum[x]-sum[y]+z+4)%2 ;
return 1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<10010;i++) pre[i]=i,sum[i]=0;
int a,b,ans,tot=0;
for(ans=0;ans<m;ans++)
{
scanf("%d %d %s",&a,&b,s);
a--;
if(mp.count(a)==0) mp[a]=tot++;
if(mp.count(b)==0) mp[b]=tot++;
int d;
if(s[0]=='e') d=0; else d=1;
if(judge(mp[a],mp[b],d)) continue;
break;
}
printf("%d\n",ans);
return 0;
}
ZOJ 3261
题意： 给你一些点，还有一些边，每个点上都有一个权值，然后有一些询问，分为两种，query a 询问与a直接或者间接想连的点中最大权值的是那个点，输出那个点，如果那个点的权值小于等于a的权值，那么就输出-1，还有另一种操作就是destroy a b意思是删除a b的关系。
做法：逆向做，首先将所有的边存起来，扫一遍被摧毁的边，将没有被摧毁的边先合并，然后逆向跑所有询问存在数组中，再输出。（这里用二维map 来标记那些边被摧毁了）
#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
using namespace std;
int rate[20100],ans[50100], pre[20100];
map<int,map<int,int> > mmp;
struct node
{
int x,y;
int type;
}op[50100];
struct path
{
int x,y;
}edge[20010];
int f(int x)
{
if(x!=pre[x]) pre[x]=f(pre[x]);
return pre[x];
}
void v(int x,int y)
{
int fx=f(x),fy=f(y);
if(fx!=fy)
{
if(rate[fx]>rate[fy])
{
pre[fy]=fx;
}
else if(rate[fx]<rate[fy]) pre[fx]=fy;
else
{
if(fx>fy) pre[fx]=fy;
else pre[fy]=fx;
}
}
}
int main()
{
int n,m,q;
char s[50];
int t=0;
while(scanf("%d",&n)!=EOF)
{
if(t++) puts("");
for(int i=0;i<n;++i) scanf("%d",&rate[i]);
mmp.clear();
scanf("%d",&m);
for(int i=0;i<m;++i)
{
scanf("%d%d",&edge[i].x,&edge[i].y);
}
scanf("%d",&q);
for(int i=0;i<q;++i)
{
scanf("%s",s);
if(s[0]=='q')
{
int a;
scanf("%d",&a);
op[i].type=0; op[i].x=a;
}
else if(s[0]=='d')
{
int a,b;
scanf("%d%d",&a,&b);
op[i].type=1; op[i].x=a; op[i].y=b;
mmp[b][a]=mmp[a][b]=1;
}
}
for(int i=0;i<=n;++i) pre[i]=i;
for(int i=0;i<m;++i)
{
int x=edge[i].x ,y=edge[i].y;
if(mmp[x][y]) continue;
v(x,y);
}
for(int i=q-1;i>=0;--i)
{
if(op[i].type==0)
{
int x=op[i].x; int fx=f(x);
if(rate[fx]>rate[x]) ans[i]=fx;
else ans[i]=-1;
}
else
{
v(op[i].x,op[i].y);
}
}
for(int i=0;i<q;++i)
{
if(op[i].type==0) printf("%d\n",ans[i]);
}
}
return 0;
}
