首页 > 代码库 > codevs.cn 2776寻找代表元 最大流解法
codevs.cn 2776寻找代表元 最大流解法
网址:http://codevs.cn/problem/2776/
题目大意: n个社团,m个人,每个社团可以有一个人担任代表,每个人可以担任多个代表,问最多有多少人是代表。
思路:可以建一个图,然后最大流(废话)。怎么建图?
先膜下神犇 orz QZZ。
样例的图大概是这样的:
图丑就不要在意啦。
s为源点,t为汇点
图中可以看出n个社团与s建一条流量为 1 的边(每个社团只选一个代表,1为限制条件),然后按照读入数据与每个人建一条流量为 1 的边(社团选了这个人就不能选了),最后每个人和t建一条流量为 1 的边。
接着最大流。
代码:
pascal:
1 var dis:array[0..410]of longint; 2 flow:array[0..410,0..410]of longint; 3 q:array[0..10000]of longint; 4 head,tail:longint; 5 n,m,x,p,z:longint; 6 i,j:longint; 7 ans:int64; 8 procedure bfs;//bfs 分层图 9 var i:longint; 10 now:longint; 11 begin 12 for i:=0 to p do 13 dis[i]:=-1; 14 dis[0]:=0; 15 head:=1; 16 tail:=1; 17 q[1]:=0; 18 while head<=tail do 19 begin 20 now:=q[head]; 21 for i:=0 to p do 22 if (flow[now,i]>0)and(dis[i]<0) then 23 begin 24 inc(tail); 25 q[tail]:=i; 26 dis[i]:=dis[now]+1; 27 end; 28 inc(head); 29 end; 30 end; 31 32 function dfs(x,mx:longint):longint;//dfs最小流 33 var k,i:longint; 34 begin 35 if x=p then exit(mx); 36 for i:=0 to p do 37 if (flow[x,i]>0)and(dis[i]=dis[x]+1) then 38 begin 39 if flow[x,i]>mx then k:=dfs(i,mx) else k:=dfs(i,flow[x,i]); 40 flow[x,i]:=flow[x,i]-k; 41 flow[i,x]:=flow[i,x]+k; 42 if k>0 then exit(k); 43 end; 44 exit(0); 45 end; 46 47 begin 48 read(n,m); 49 p:=n+m+1;//p为总节点数 0 为源点s p 为汇点t 50 for i:=1 to n do 51 begin 52 x:=1; 53 while x<>0 do 54 begin 55 read(x); 56 if x<>0 then flow[i,x+n]:=1;//建社团与人数的边,因为不能编号相同,所以 1~n 为社团 n+1~n+m 为人
57 end; 58 flow[0,i]:=1;//建s与社团的边 59 end; 60 for i:=1 to m do 61 flow[n+i,p]:=1;//建人与t的边 i还是要加n 才是人的编号 62 while true do //最大流 63 begin 64 bfs; 65 if dis[p]<0 then break; 66 repeat 67 z:=dfs(0,maxint); 68 ans:=ans+z; 69 until z>0; 70 end; 71 writeln(ans); 72 end.
C++:
还是没代码,有时间补上。
望原谅。
最大流主要还是建图。然后蒟蒻我又水了一篇博客。
codevs.cn 2776寻找代表元 最大流解法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。