NOI的题目,并查集的高级应用,很好玩的一个题目。题目:http://acm.pku.edu.cn/JudgeOnline/problem?id=1182
#include "stdio.h"
int num[50005];
int dis[50005];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int relation1[3]=
{0,1,2}; /**//*正权*/
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int relation2[3]=
{0,2,1}; /**//*负权*/
void make(int p)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i;
for(i=0;i<p;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
num[i]=-1;
dis[i]=0;
}
}
int find(int p)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i;
if(num[p]<0)return p;
i=find(num[p]);
dis[p]=dis[p]+dis[num[p]];
num[p]=i;
return i;
}
void un(int a,int b,int len)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int ra=find(a);
int rb=find(b);
num[rb]=ra;
dis[rb]=dis[a]+len-dis[b];
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int n,k,i;
int x,y,d;
int rx,ry;
int dx,dy;
int count;
scanf("%d%d",&n,&k);
make(n);count=0;
for(i=0;i<k;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d%d%d",&d,&x,&y);
if(x>n||y>n)count++;
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
rx=find(x-1);
ry=find(y-1);
if(d==1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(rx!=ry)un(x-1,y-1,0);
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(dis[x-1]<0)dx=relation2[(-dis[x-1])%3];
else dx=relation1[dis[x-1]%3];
if(dis[y-1]<0)dy=relation2[(-dis[y-1])%3];
else dy=relation1[dis[y-1]%3];
if(dx!=dy)count++;
}
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(rx!=ry)un(x-1,y-1,1);
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(dis[x-1]<0)dx=relation2[(-dis[x-1])%3];
else dx=relation1[dis[x-1]%3];
if(dis[y-1]<0)dy=relation2[(-dis[y-1])%3];
else dy=relation1[dis[y-1]%3];
if((dx+1)%3!=dy)count++;
}
}
}
}
printf("%d\n",count);
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)