本题在洛谷上的链接：https://www.luogu.org/problemnew/show/P1525
应该说这道题不算太难，但挺考察代码实现能力。首先我们应该是本着贪心的原则，让怨气值大的罪犯尽量分开，这样就牵扯到将n个点划分成两部分的问题。做法有两种，并查集或二分答案+二分图染色。值得一提的是并查集，这里get到了一个新技能：补集。
一开始，我判断的方法是，将不能在一起的罪犯加入到一个并查集，如果遇到冲突（两个罪犯原先就在一个并查集里）则为判定失败，这样只有60分。哪里不对呢？举个简单的例子，A和B不能在一起，B和C不能在一起，C和D不能在一起，按照上面的方法，A和D也不能在一起，但实际上A和D可以在一起，这牵扯到两个点之间隔着奇数个点还是偶数个点。
然后看到dalao题解里有种方法是使用补集，就是把不能和某个罪犯在一起的罪犯放到一起，因为只有两个牢房，如果放到一起的罪犯不能在一起，这就是真的冲突了。
1 #include<cstdio> 2 #include<cctype> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 inline int get_num() { 8 int num;char c; 9 while((c=getchar())==‘\n‘||c==‘ ‘||c==‘\r‘); 10 num=c-‘0‘; 11 while(isdigit(c=getchar())) num=num*10+c-‘0‘; 12 return num; 13 } 14 const int maxn=2e4+5,maxm=1e5+5; 15 int n,m,fa[2*maxn],d[maxn]; 16 struct edge { 17 int u,v,w; 18 bool operator < (const edge& rhs) const { 19 return w>rhs.w; 20 } 21 } E[maxm]; 22 int f(int i) { 23 if(fa[i]==i) return i; 24 return fa[i]=f(fa[i]); 25 } 26 int main() { 27 n=get_num();m=get_num(); 28 for(int i=1;i<=m;++i) 29 E[i].u=get_num(),E[i].v=get_num(),E[i].w=get_num(); 30 sort(E+1,E+m+1); //将边按降序排序 31 for(int i=1;i<=2*n;++i) fa[i]=i; 32 for(int i=1;i<=m;++i) { 33 int u=E[i].u,v=E[i].v; 34 if(f(u)==f(v)) { 35 printf("%d",E[i].w); 36 return 0; 37 } 38 fa[fa[u]]=fa[f(v+n)]; //将不能和v在一起的和v+n放在一起 39 fa[fa[v]]=fa[f(u+n)]; //同上 40 } 41 printf("0"); 42 return 0; 43 }
原文：https://www.cnblogs.com/Mr94Kevin/p/9581992.html
