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
2 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  begin
107  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  begin
113  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 do
118   begin
119   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  begin
126  maxflow:=0;
127  dinic;
128  tarjan;
129  ans:=0;
130  for i:=1 to num do
131   begin
132   if (e[a[i]].v<>0) and (scc[x[i]]<>scc[y[i]]) then
133     begin
134     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 begin
142  assign(input,'input.txt');assign(output,'output.txt');
143  reset(input);rewrite(output);
144  init;
145  main;
146  close(input);close(output);
147 end.

View Code