记录编号 | 39297 | 评测结果 | AAAAAAAAAA | ||
---|---|---|---|---|---|
题目名称 | 最小最大生成树 | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | Pascal | 运行时间 | 0.883 s | ||
提交时间 | 2012-07-08 16:55:19 | 内存使用 | 14.97 MiB | ||
program mstmn; type flowedge=record v,c:longint; next,against:longint; end; var n,i,j,k,l,m,s,t,value,flowtop,maxflow,minE,minH,arug,p:longint; flowedges:array[1..800008] of flowedge; u,v,e:array[1..200000] of longint; now,height,flowh,gap:array[0..20008] of longint; find:boolean; function min(x,y:longint):longint; begin if x<y then exit(x) else exit(y); end; procedure insertflowE(u,v,against,c:longint); begin flowedges[flowtop].v:=v;flowedges[flowtop].against:=against; flowedges[flowtop].next:=flowh[u]; flowh[u]:=flowtop; flowedges[flowtop].c:=c; inc(flowtop); end; procedure SAP(k,delta:longint); var x:flowedge; begin if k=t then begin find:=true; arug:=delta; inc(maxflow,arug); exit; end; while now[k]<>0 do begin x:=flowedges[now[k]]; if (height[x.v]+1=height[k]) and (x.c>0) then begin SAP(x.v,min(delta,x.c)); if height[s]=n then exit; if find then break; end; now[k]:=x.next; end; if find then begin dec(flowedges[now[k]].c,arug); inc(flowedges[x.against].c,arug); end else begin minh:=n-1; p:=flowh[k]; minE:=p; while p<>0 do begin x:=flowedges[p]; if (height[x.v]<minh) and (x.c>0) then begin minh:=height[x.v]; minE:=p; end; p:=x.next; end; dec(gap[height[k]]); if gap[height[k]]=0 then height[s]:=n; inc(gap[minh+1]); height[k]:=minh+1; now[k]:=minE; end; end; begin // OpenFile assign(input,'mstmn.in'); reset(input); assign(output,'mstmn.out'); rewrite(output); // Input readln(n,m); for l:=1 to m do readln(u[l],v[l],e[l]); readln(s,t,value); // CalMinST flowtop:=1; for i:=1 to m do if e[i]>value then begin insertflowE(u[i],v[i],flowtop+1,1); insertflowE(v[i],u[i],flowtop-1,0); insertflowE(v[i],u[i],flowtop+1,1); insertflowE(u[i],v[i],flowtop-1,0); end; gap[0]:=n; now:=flowh; repeat find:=false; SAP(s,maxlongint); until height[s]=n; // CalMaxST fillchar(height,sizeof(height),0); fillchar(gap,sizeof(height),0); fillchar(flowh,sizeof(flowh),0); fillchar(flowedges,sizeof(flowedges),0); flowtop:=1; for i:=1 to m do if e[i]<value then begin insertflowE(u[i],v[i],flowtop+1,1); insertflowE(v[i],u[i],flowtop-1,0); insertflowE(v[i],u[i],flowtop+1,1); insertflowE(u[i],v[i],flowtop-1,0); end; gap[0]:=n; now:=flowh; repeat find:=false; SAP(s,maxlongint); until height[s]=n; // Print writeln(maxflow); // CloseFile close(input); close(output); end.