P1525 关押罪犯（洛谷）

前几天没做题，神经有点错乱，感觉一片虚无。今天开始继续写博客。

题目描述

S 城现有两座监狱，一共关押着N名罪犯，编号分别为1-N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 c 的冲突事件。

每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

在详细考察了N名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。

那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

输入格式

每行中两个数之间用一个空格隔开。第一行为两个正整数N,M分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的 M 行每行为三个正整数 aj，bj，cj，表示aj号和bj号罪犯之间存在仇恨，其怨气值为 cj。数据保证aj,bj,cj<10^9，且每对罪犯组合只出现一次。

输出格式

共 11 行，为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出 0。

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

【输入输出样例说明】罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是 3512（由 2 号和 3 号罪犯引发）。其他任何分法都不会比这个分法更优。

【数据范围】

对于30%的数据 n<=15

对于70%的数据 n<=2000,m<=50000

对于100%的数据 n<=20000,m<=100000

不难看出这个题是并查集，就是把罪犯们分成2份，然后查看最高的的怨气值最小就好了。

怎么做到这一点呢？

其实排个序就好了。

怨念值从大到小排序，查找到一组罪犯在最优情况下还是要在一个监狱，那这个就是最大可能性。

int px(struct hehe a1,struct hehe a2)

{

	return a1.z>a2.z;//按照怨念值从大到小排序。

}

cin>>n>>m;

for(int i=1;i<=n;i++)

{

	a[i]=i;//每一个小并查集的头头都是自己。

}

for(int i=0;i<m;i++)

{

	cin>>sz[i].t>>sz[i].w>>sz[i].z;//a，b，c。

}

什么是最优呢？

你只要尽可能不让怨念值大的罪犯分到一起就好了。

这时候，我们要利用到一个重要的观点：敌人的敌人是朋友(大多数情况)

所以我们只要找到敌人的敌人的爸爸是谁解决了。

如果出现了一个从来没出现过和敌人的人，那他就是这个人的第一个敌人，标记起来，以后这个人的敌人就会和他分到一组，直到出现第三种情况。

if(cr[sz[i].t]==0)//sz[i].t没出现过敌人，cr是仇人的意思，用来存这个人的第一个敌人。

{

	cr[sz[i].t]=sz[i].w;

}else

{

	add(sz[i].w,cr[sz[i].t]);//这个人有过敌人，把我和敌人的敌人合并。

}

if(cr[sz[i].w]==0)//同上

{

	cr[sz[i].w]=sz[i].t;

}else

{

	add(sz[i].t,cr[sz[i].w]);

}

处理完正常人，我们继续向后查找，直到遇到一个很变态的人，三角得罪（敌人的敌人也是他的敌人的变态）

这样的话2个监狱都容不下他，然后就没办法了，但由于我们是按照怨念值从大到小排序，所以直接输出这个的怨念值就好了。

if(f(sz[i].t)==f(sz[i].w))//在这个组说明之前肯定有一个和他关系更加不好的人在另一个组，但这个组也有跟他关系不好的人，没办法了。

{

    cout<<sz[i].z<<endl;

    return 0;

}

如果没有这种情况，记得输出0。（这个很重要哦）

看似是2个并查集，但我感觉其中有一些根本没关系，准确是由多个并查集组合成的2个。所以可能会有很多开头，这不重要。反正他们可以随便组合。

全部代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<cstring>

using namespace std;

long long a[20005],cr[20005];

struct hehe

{

	long long t,w,z;//犯人怨念信息数组

}sz[100005];

int px(struct hehe a1,struct hehe a2)

{

	return a1.z>a2.z;//从大到小排序

}

int f(int wz)//寻找爸爸

{

	if(a[wz]==wz)

	{

		return wz;

	}

	return f(a[wz]);

}

void add(int b1,int b2)//2个集合合成一个。

{

	a[f(b1)]=f(b2);//这样以后查找好像快一点。

}

long long n,m;

int main()

{

	cin>>n>>m;

	for(int i=1;i<=n;i++)

	{

		a[i]=i;//每个小并查集的头头都是自己。

	}

	for(int i=0;i<m;i++)

	{

		cin>>sz[i].t>>sz[i].w>>sz[i].z;

	}

	sort(sz,sz+m,px);

	for(int i=0;i<m;i++)

	{

		if(f(sz[i].t)==f(sz[i].w))//遇到了一个讨厌的人。

		{

			cout<<sz[i].z<<endl;

			return 0;//遇到了一定要return 0哦。

		}

		if(cr[sz[i].t]==0)//sz[i].t之前没见到敌人。sz[i].w是他的第一个敌人。

		{

			cr[sz[i].t]=sz[i].w;

		}else

		{

			add(sz[i].w,cr[sz[i].t]);//之前有过敌人，合并。

		}

		if(cr[sz[i].w]==0)//同上

		{

			cr[sz[i].w]=sz[i].t;

		}else

		{

			add(sz[i].t,cr[sz[i].w]);

		}

	}

	cout<<0<<endl;//没有讨厌的人一定要输出0，很重要，很重要，很重要。

	return 0;

}

好的，就这么结束了，写个博客感觉挺不错的。

巴特西