首页 > 代码库 > CH Round #17 舞动的夜晚
CH Round #17 舞动的夜晚
舞动的夜晚 CH Round #17
描述
L公司和H公司举办了一次联谊晚会。晚会上，L公司的N位员工和H公司的M位员工打算进行一场交际舞。在这些领导中，一些L公司的员工和H公司的员工之间是互相认识的，这样的认识关系一共有T对。舞会上，每位员工会尝试选择一名Ta认识的对方公司的员工作为舞伴，并且每位员工至多跳一支舞。完成的交际舞的数量越多，晚会的气氛就越热烈。顾及到晚会的气氛，员工们希望知道，哪些员工之间如果进行了交际舞，就会使整场晚会能够完成的交际舞的最大数量减小。
输入格式
第一行三个整数N、M、T。
接下来T行每行两个整数x、y，表示L公司的员工x和H公司的员工y互相认识。
输出格式
第一行一个整数cnt，表示进行了交际舞后会使整场晚会能够完成的交际舞的最大数量减小的员工有多少对。
第二行cnt个整数，升序输出这样的一对员工的认识关系的编号（他们的认识关系是在输入数据中读入的第几条认识关系）。如果cnt=0，输出一个空行。
样例输入
3 3 61 12 12 23 13 23 3
样例输出
32 4 5
数据范围与约定
- 对于50%的数据，1<=N,M<=100，1<=T<=1000。
- 对于100%的数据，1<=N,M<=10000，1<=T<=100000，1<=x<=N，1<=y<=M
题解：
其实我很想问，这范围是给网络流的？忽然想到，白书上有句话---可以证明，对于二分图最大匹配这样的特殊图，dinic算法的复杂度为O（sqrt（n）*m）；
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
二分图的可行边/必须边： 先用Dinic求出任意一组最大匹配。 建一张新图：对于匹配边(u,v)，v到u连边；非匹配边u到v连边； 对于匹配的左部点u，u到S连边；未匹配的左部点u，S到u连边； 对于匹配的右部点v，T到v连边；未匹配的右部点v，v到T连边。 用Tarjan求强连通分量，若(u,v)是匹配边或者u,v在同一个SCC中——可行边；若(u,v)是匹配边且u,v不在同一个SCC中——必须边。---lyd
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
其实后面的一大坨构图就是一句话---残量网络
直接在残量网络里tarjan，然后扫一遍即可
ps：这题教育我，即使感觉数组不会越界，也一定要把数组开大，不爆内存就好！
代码：
1 const inf=maxlongint; 2 type node=record 3 from,go,next,v:longint; 4 end; 5 var tot,i,j,n,m,maxflow,l,r,s,t,ans,num,cnt,ti,top:longint; 6 h,head,q,cur,a,dfn,low,sta,scc,x,y:array[0..500000] of longint; 7 e:array[0..5000000] of node; 8 b:array[0..500000] of boolean; 9 function min(x,y:longint):longint; 10 begin 11 if x<y then exit(x) else exit(y); 12 end; 13 procedure ins(x,y,z:longint); 14 begin 15 inc(tot); 16 e[tot].from:=x;e[tot].go:=y;e[tot].v:=z;e[tot].next:=head[x];head[x]:=tot; 17 end; 18 procedure insert(x,y,z:longint); 19 begin 20 ins(x,y,z);ins(y,x,0); 21 end; 22 function bfs:boolean; 23 var i,x,y:longint; 24 begin 25 fillchar(h,sizeof(h),0); 26 l:=0;r:=1;q[1]:=s;h[s]:=1; 27 while l<r do 28 begin 29 inc(l); 30 x:=q[l]; 31 i:=head[x]; 32 while i<>0 do 33 begin 34 y:=e[i].go; 35 if (e[i].v<>0) and (h[y]=0) then 36 begin 37 h[y]:=h[x]+1; 38 inc(r);q[r]:=y; 39 end; 40 i:=e[i].next; 41 end; 42 end; 43 exit (h[t]<>0); 44 end; 45 function dfs(x,f:longint):longint; 46 var i,y,used,tmp:longint; 47 begin 48 if x=t then exit(f); 49 used:=0; 50 i:=cur[x]; 51 while i<>0 do 52 begin 53 y:=e[i].go; 54 if (h[y]=h[x]+1) and (e[i].v<>0) then 55 begin 56 tmp:=dfs(y,min(e[i].v,f-used)); 57 dec(e[i].v,tmp);if e[i].v<>0 then cur[x]:=i; 58 inc(e[i xor 1].v,tmp); 59 inc(used,tmp); 60 if used=f then exit(f); 61 end; 62 i:=e[i].next; 63 end; 64 if used=0 then h[x]:=-1; 65 exit(used); 66 end; 67 procedure dinic; 68 begin 69 while bfs do 70 begin 71 for i:=s to t do cur[i]:=head[i]; 72 inc(maxflow,dfs(s,inf)); 73 end; 74 end; 75 procedure dfs(x:longint); 76 var i,y,z:longint; 77 begin 78 inc(ti);dfn[x]:=ti;low[x]:=ti;inc(top);sta[top]:=x; 79 i:=head[x]; 80 while i<>0 do 81 begin 82 y:=e[i].go; 83 if e[i].v<>0 then 84 begin 85 if dfn[y]=0 then 86 begin 87 dfs(y); 88 low[x]:=min(low[x],low[y]); 89 end 90 else if scc[y]=0 then low[x]:=min(low[x],dfn[y]); 91 end; 92 i:=e[i].next; 93 end; 94 if low[x]=dfn[x] then 95 begin 96 inc(cnt); 97 while true do 98 begin 99 z:=sta[top];dec(top);100 scc[z]:=cnt;101 if z=x then break;102 end;103 end;104 end;105 procedure tarjan;106 begin107 ti:=0;cnt:=0;ti:=0;108 fillchar(dfn,sizeof(dfn),0);109 for i:=s to t do if dfn[i]=0 then dfs(i);110 end;111 procedure init;112 begin113 tot:=1;114 readln(n,m,num);115 s:=0;t:=n+m+1;116 for i:=1 to n do insert(s,i,1);117 for i:=1 to num do118 begin119 readln(x[i],y[i]);inc(y[i],n);120 a[i]:=tot+1;insert(x[i],y[i],1);121 end;122 for i:=n+1 to n+m do insert(i,t,1);123 end;124 procedure main;125 begin126 maxflow:=0;127 dinic;128 tarjan;129 ans:=0;130 for i:=1 to num do131 begin132 if (e[a[i]].v<>0) and (scc[x[i]]<>scc[y[i]]) then133 begin134 b[i]:=true;inc(ans);135 end;136 end;137 writeln(ans);138 if ans=0 then writeln else for i:=1 to num do if b[i] then write(i,‘ ‘);139 end;140 141 begin142 assign(input,‘input.txt‘);assign(output,‘output.txt‘);143 reset(input);rewrite(output);144 init;145 main;146 close(input);close(output);147 end.