首页 > 代码库 > 关押罪犯（noip2010）
关押罪犯（noip2010）
解法：
（1）搜索（30分）
（2）二分（此题属于最大值最小问题）
（3）贪心+并查集
下面着重说一下“贪心+并查集”
因为有A、B两座监狱，每个犯人不是在A，就是在B监狱。
至于每个犯人在那个监狱，我们可以人为的指定，但在指定时要考虑和他有怨气的所有人，太复杂了！
反过来，我们可以从全局考虑：用x0表示x的反集合,y0表示y的反集合,也就是说如果不跟x同集合那就一定跟x0同集合,同理,如果不跟y同集合就一定跟y0同集合...
这样先排序,从大到小往不同的集合中添加边的两个端点,每次判断是否有冲突,若有冲突（说明该边的两个端点在前面比他大的边的分配中已经分配到同一个集合，那么该边就是符合要求的最大边）,那么就输出,否则合并..
type node=record x,y,data:longint; end;var n,m:longint; bo:boolean; a:array[0..100100]of node; f:array[0..40100] of longint; procedure init; var i:longint; begin bo:=false; readln(n,m); for i:=1 to m do readln(a[i].x,a[i].y,a[i].data); end; procedure qsort(l,r:longint); var mid,i,j:longint;t:node; begin mid:=a[(L+R)div 2].data; i:=l;j:=r; while i<j do begin while a[i].data<mid do inc(i); while a[j].data>mid do dec(j); if i<=j then begin t:=a[i];a[i]:=a[j];a[j]:=t; inc(i);dec(j); end; end; if i<r then qsort(i,r); if j>l then qsort(l,j); end; function find(x:longint):longint; begin if f[x]=x then exit(x); if f[f[x]]=f[x] then exit(f[x]); find:=find(f[x]); f[x]:=find; end; procedure main; var i,x,y,x0,y0,nn:longint; begin nn:=n+n; for i:=1 to nn do f[i]:=i; qsort(1,m); for i:=m downto 1 do begin x:=a[i].x;y:=a[i].y;x0:=n+x;y0:=n+y; x:=find(x);y:=find(y);x0:=find(x0);y0:=find(y0); if (x=y){or(x0=y0)} then begin writeln(a[i].data);bo:=true;break;end; if x<>y0 then f[x]:=y0; if y<>x0 then f[y]:=x0; end; end;begin assign(input,‘prison.in‘);reset(input); assign(output,‘prison.out‘);rewrite(output); init; main; if not bo then write(0); close(input);close(output);end.
关押罪犯（noip2010）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。