题目描述
S 城现有两座*，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一*，他们俩之间会发生摩擦，并造成影响力为c 的冲突事件。
每年年末，警察局会将本年内*中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。
在详细考察了N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座*内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一*内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。
那么，应如何分配罪犯，才能使Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？
输入输出格式
输入格式：
输入文件的每行中两个数之间用一个空格隔开。第一行为两个正整数N 和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的M 行每行为三个正整数aj，bj，cj，表示aj 号和bj 号罪犯之间存在仇恨，其怨气值为cj。数据保证1<aj=<=bj<=N ，0 < cj≤ 1,000,000,000，且每对罪犯组合只出现一次。
输出格式：
共1 行，为Z 市长看到的那个冲突事件的影响力。如果本年内*中未发生任何冲突事件，请输出0。
输入输出样例
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
3512
说明
【输入输出样例说明】罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是3512（由2 号和3 号罪犯引发）。其他任何分法都不会比这个分法更优。
【数据范围】对于30%的数据有N≤ 15。对于70%的数据有N≤ 2000，M≤ 50000。对于100%的数据有N≤ 20000，M≤ 100000。
这里相当于把每个罪犯分成两个点，分别表示一个正的罪犯和一个反的罪犯（大概这么理解吧），然后将a与b+n合到一个集表示两个人可以放在一个*里面（即正的罪犯可以和反的仇恨的罪犯一起），那么如果查到两个罪犯在一个集里面时，则代表向仇恨的两个人如果要满足前面的所有操作，必须在一个*里面，所以只能输出当前的c，因为是从大到小排的，所以可以过
#include<stdio.h>
#define maxn 150000
int a[maxn],b[maxn],f[maxn],w[maxn]; int get(int x){
if(f[x]==x) return x;
f[x]=get(f[x]);
return f[x];
} void sort(int n,int m){
int i=n,j=m,k=w[(i+j)/],h;
while(i<=j){
while(w[i]>k) i++;
while(w[j]<k) j--;
if(i<=j){
h=a[i],a[i]=a[j],a[j]=h;
h=b[i],b[i]=b[j],b[j]=h;
h=w[i],w[i]=w[j],w[j]=h;
i++; j--;
}
}
if(i<m) sort(i,m);
if(j>n) sort(n,j);
}
int main(){
int n,m;
scanf("%d %d",&n,&m);
for(int i=;i<=*n;i++) f[i]=i;
for(int i=;i<=m;i++) scanf("%d %d %d",&a[i],&b[i],&w[i]);
sort(,m);
for(int i=;i<=m;i++){
int x=get(a[i]),y=get(b[i]);
if(x==y){
printf("%d",w[i]);
return ;
}
f[x]=get(n+b[i]);
f[y]=get(n+a[i]);
}
printf("");
return ;
}
题目描述
动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B
吃 C，C 吃 A。
现有 N 个动物，以 1 － N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道
它到底是哪一种。
有人用两种说法对这 N 个动物所构成的食物链关系进行描述：
第一种说法是“1 X Y”，表示 X 和 Y 是同类。
第二种说法是“2 X Y”，表示 X 吃 Y 。
此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真
的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
• 当前的话与前面的某些真的话冲突，就是假话
• 当前的话中 X 或 Y 比 N 大，就是假话
• 当前的话表示 X 吃 X，就是假话
你的任务是根据给定的 N 和 K 句话，输出假话的总数。
输入输出格式
输入格式：
从 eat.in 中输入数据
第一行两个整数，N，K，表示有 N 个动物，K 句话。
第二行开始每行一句话（按照题目要求，见样例）
输出格式：
输出到 eat.out 中
一行，一个整数，表示假话的总数。
输入输出样例
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
3
这题显然要用并查集。因为只有3种动物，我的方法是对每个动物x建立3个集合：x表示与x同类的动物，x+n表示要x吃的动物，x+2*n表示吃x的动物。
对于每个读入的描述D X Y，做以下处理：
如果X或Y不再区间[1,n]中，这句是假话。
- D为1
如果x+n或x+2*n与y在同一个集合中说明已知x和y不是同一种动物，这句是假话；
否则，分别将x与y，x+n与y+n，x+2*n与y+2*n合并。
- D为2
如果x与y在同一个集合中，说明已知x和y是同一种动物，这句是假话；
如果x+2*n与y在同一个集合中，说明已知y吃x，这句是假话；
否则，分别将x与y+2*n，x+n与y，x+2*n与y+n合并。
#include<stdio.h>
int f[];
int get(int x){
if(f[x]==x) return x;
f[x]=get(f[x]);
return f[x];
}
int main(){
int n,m;
scanf("%d %d",&n,&m);
for(int i=;i<=*n;i++) f[i]=i;
int ans=;
for(int i=;i<=m;i++){
int x,y,num;
scanf("%d %d %d",&num,&x,&y);
if(num==&&x==y || x>n || y>n){
ans++; continue;
}
if(num==){
if(get(x+n)==get(y)||get(x+*n)==get(y)||get(x)==get(y+n)||get(x)==get(y+*n)){
ans++;
continue;
}
f[get(x)]=get(y);
f[get(x+n)]=get(y+n);
f[get(x+*n)]=get(y+*n);
}
else{
if(get(x)==get(y)||get(x+*n)==get(y)){
ans++;
continue;
}
f[get(x)]=get(y+*n);
f[get(x+n)]=get(y);
f[get(x+*n)]=get(y+n);
}
}
printf("%d",ans);
return ;
}