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<=1000000000,且每对罪犯组合只出现一次。
输出文件共1行，为Z市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出0。
每个测试点1s
分配方法：市长看到的冲突事件影响力是3512（由2号和3号罪犯引发）。其他任何分法都不会比这个分法更优。
对于30%的数据有N≤15。
对于70%的数据有N≤2000，M≤50000。
对于100%的数据有N≤20000，M≤100000。
noip2010提高组复赛
解法1
并查集+贪心
贪心+并查集 opp[x]=y代表x和y有仇
先排序（贪心） 然后并查集 读入x,y 如果opp[x]之前有值 就把 新来的y和x并在一起 如果x,y本来就并在一起 那么这个就是不可避免的 直接输出
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #define N 20005 #define M 100005 using namespace std; int m,n;int fa[N]; int opp[M]; struct node{ int x,y,c; }p[M]; int findf(int x){//并查集 的查找 return fa[x]==x?x:fa[x]=findf(fa[x]); } int merge(int x,int y){//并查集 的合并 fa[findf(x)]=findf(y); } bool cmp(node xx,node yy){ return xx.c>yy.c; } void read(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].c); } int main(){ read(); sort(p+1,p+1+m,cmp); for(int i=1;i<=n;i++)//并查集的初始化 fa[i]=i; for(int i=1;i<=m;i++){ int x=p[i].x ;int y=p[i].y; int fx=findf(x),fy=findf(y); if(fx==fy){ printf("%d",p[i].c);return 0; } if(opp[x]!=0){ merge(opp[x],y); } if(opp[y]!=0){ merge(opp[y],x); } opp[x]=findf(y);//opp中始终存的是对立的罪犯群体的祖先 opp[y]=findf(x); } printf("0"); return 0; } 2.二分答案+染色
这题求最大的冲突值最小 很容易就想到二分答案
用前向星存图 二分一个答案 dfs图 如果这个答案小于这个边的权值 那么这个边的两个端点（罪犯）就不能在一个监狱 监狱号为1和2 如果不在一个监狱 则另一个的监狱为3-col[x]
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #define M 100005 #define N 20005 using namespace std; int p[N],cnt=0,col[N]; int n,m;int w[M],ans=0; struct node{ int b; int nt; int w; }e[2*M]; void ins(int x,int y,int w){ cnt++; e[cnt].b=y;e[cnt].w=w;e[cnt].nt=p[x];p[x]=cnt; } void insert(int x,int y,int w){ins(x,y,w);ins(y,x,w);} void read(){ scanf("%d%d",&n,&m); int x,y,z; for(int i=1;i<=m;i++){ scanf("%d%d",&x,&y,&z); insert(x,y,z); w[i]=z; } } bool dfs(int x,int pd){ for(int i=p[x];i;i=e[i].nt){ if(e[i].w<=pd) continue; int v=e[i].b; if(col[v]==col[x]) return false; if(!col[v]){ col[v]=3-col[x]; if(!dfs(v,pd)) return false; } } return true; } bool check(int pd){ for(int i=1;i<=n;i++){ if(!col[i]) col[i]=1; if(!dfs(i,pd)) return false; } return true; } int main(){ read(); sort(w+1,w+1+m); int l=1,r=m; while(l<=r){ int m=(l+r)/2; int pd=w[m]; memset(col,0,sizeof(col)); if(!check(pd)) l=m+1; else { ans=w[m]; r=m-1; } } if(l==1&&r<1) printf("0"); else printf("%d",ans); return 0; }
