爱华网2011.7.14 21:29
终于会做NOIP2010第三题了。
关押罪犯这道题的算法是二分答案+二分图染色。复杂度O(nlogm).
二分答案就是先把所有的罪犯之间的关系按照怨气值排序。然后开始二分怨气值，就是以中间的关系开始，要想使中间的关系成立就必须要让他右边的比他怨气值大的关系无法成立，否则中间的关系不成立。那么判定右边的关系不成立就要用到二分图染色。就好象tyvj1351这道题似的，需要用到深搜。就是假如有x1,x2,x3三个点，假如x1与x2不能在一起，那么x1标1，x2标0，x2与x3不能在一起，x2已经是0了，x3必须是1，并且x3和x1不能在一起，所以x3，x1都是1，关系出现矛盾，就无法成立关系，就是false，中间的关系不能成立，所以中间的怨气值也不是最小，需要向右继续二分，如果成立就向左。二分复杂度logm，枚举每个点的关系深搜是n，所以nlogm。关系储存的时候用边表存，否则会超时。
注意：边表一定要存两遍。数据范围开成2倍的m。
代码：
type
bian=record
y,next,data:longint;
end;
var
score,tot,n,m:longint;
map:Array[0..200000] ofbian;
first,b:array[0..20000] oflongint;
a:Array[0..200000] oflongint;
panduan:boolean;
procedure qsort(l,r:longint);
var
i,j,mid,t:longint;
begin
i:=l;
j:=r;
mid:=a[(l+r) div 2];
repeat
while a[i]<mid do inc(i);
while a[j]>mid do dec(j);
if i<=j then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
inc(i);
dec(j);
end;
untili>j;
if i<r thenqsort(i,r);
if l<j thenqsort(l,j);
end;
procedure insert(x,y,data:longint);
begin
inc(tot);
map[tot].y:=y;
map[tot].data:=data;
map[tot].next:=first[x];
first[x]:=tot;
end;
procedure init;
var
t1,t2,t3,i:longint;
begin
fillchar(first,sizeof(first),0);
tot:=0;
readln(n,m);
for i:=1 to m do
begin
readln(t1,t2,t3);
insert(t1,t2,t3);
insert(t2,t1,t3);
a[i+1]:=t3;
end;
a[1]:=0;{初始化，因为存在无事件发生输出0，所以二分时当l=r=1是无法继续二分，所以就a[1]=0}
qsort(1,m+1);{一定是m+1,因为多了一个0}
end;
procedure dfs(x,data:longint);
var
t:longint;
begin
if panduan=false thenexit;{关系不成立所以退出不继续深搜}
b[x]:=data;{这个点染色}
t:=first[x];{找这个点所连的点}
while t>0do
begin
if map[t].data>scorethen{要使mid右边的关系不成立,所以深搜右边的点}
begin
if b[map[t].y]=-1 thendfs(map[t].y,1-data){如果这个点没有被染色就染不同于这个点的色}
else if b[map[t].y]=data then{如果染色并且颜色相同说明关系不成立,判断为false,退出}
begin
panduan:=false;
exit;
end;
end;
t:=map[t].next;
end;
end;
function judge(middle:longint):boolean;
var
i:longint;
begin
fillchar(b,sizeof(b),255);{初始化图的颜色,255为-1,即没有被染色}
panduan:=true;{判断初始化为成立}
score:=a[middle];{存储mid的怨气值}
for i:=1 to n do{枚举每个点}
begin
if b[i]=-1then{只要是没有被染色,就随便染一个颜色就行了,因为如果染色早就在之前染色了,没有被染色说明这是另一个图不与
之前的相连}
dfs(i,0);{深搜这个点}
end;
exit(panduan);{返回判断值}
end;
procedure main;
var
mid,l,r:longint;
begin
l:=1;
r:=m+1;{左右边界初始化}
while l<rdo
begin
mid:=(l+r) div 2;
if judge(mid)=true then{如果成立向左找更优的}
begin
r:=mid;
end
else{不成立就向左右找更差的}
begin
l:=mid+1;
end;
end;
writeln(a[l]);{输出答案,因为最后mid如果不成立最优值就是a[l]了}
end;
begin
/// assign(input,'in.txt');reset(input);
//assign(output,'out.txt');rewrite(output);
init;
main;
// close(input);close(output);
end.
