首页 > 代码库 > BZOJ1934: [Shoi2007]Vote 善意的投票
BZOJ1934: [Shoi2007]Vote 善意的投票
1934: [Shoi2007]Vote 善意的投票
Time Limit: 1 Sec Memory Limit: 64 MBSubmit: 1076 Solved: 660
[Submit][Status]
Description
幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说,这个问题并不是很重要,于是他们决定发扬谦让精神。虽然每个人都有自己的主见,但是为了照顾一下自己朋友的想法,他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。 我们的问题就是,每位小朋友应该怎样投票,才能使冲突数最小?
Input
第一行只有两个整数n,m,保证有2≤n≤300,1≤m≤n(n-1)/2。其中n代表总人数,m代表好朋友的对数。文件第二行有n个整数,第i个整数代表第i个小朋友的意愿,当它为1时表示同意睡觉,当它为0时表示反对睡觉。接下来文件还有m行,每行有两个整数i,j。表示i,j是一对好朋友,我们保证任何两对i,j不会重复。
Output
只需要输出一个整数,即可能的最小冲突数。
Sample Input
3 3
1 0 0
1 2
1 3
3 2
1 0 0
1 2
1 3
3 2
Sample Output
1
HINT
在第一个例子中,所有小朋友都投赞成票就能得到最优解
Source
Day2
题解:
这题怎么这么神!
膜拜hzwer的题解:
构建源S,汇T
然后S->一开始投同意的xpy,一开始投反对票的xpy ->T
流量均为1
然后对于一个朋友关系(a,b) 添加双向边,流量依然为1
最后割即为冲突数
(1) 冲突数不大于 n:
很显然,哪怕所有xpy之间都存在朋友关系,xpy可以通过改变(或不改变)原先的决定到达全“同意”或全“否定”,那么朋友之间的冲突数为0,而未被自己先前决定的冲突数不大于n
(2) “同意”集合和“否定”集合之间的边全部是朋友关系
(3) 冲突是同意与不同意之间的割
然后S->一开始投同意的xpy,一开始投反对票的xpy ->T
流量均为1
然后对于一个朋友关系(a,b) 添加双向边,流量依然为1
最后割即为冲突数
(1) 冲突数不大于 n:
很显然,哪怕所有xpy之间都存在朋友关系,xpy可以通过改变(或不改变)原先的决定到达全“同意”或全“否定”,那么朋友之间的冲突数为0,而未被自己先前决定的冲突数不大于n
(2) “同意”集合和“否定”集合之间的边全部是朋友关系
(3) 冲突是同意与不同意之间的割
代码:
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,x,y:longint; 6 h,head,q,cur:array[0..1000] of longint; 7 e:array[0..200000] of node; 8 function min(x,y:longint):longint; 9 begin 10 if x<y then exit(x) else exit(y); 11 end; 12 procedure ins(x,y,z:longint); 13 begin 14 inc(tot); 15 e[tot].from:=x;e[tot].go:=y;e[tot].v:=z;e[tot].next:=head[x];head[x]:=tot; 16 end; 17 procedure insert(x,y,z:longint); 18 begin 19 ins(x,y,z);ins(y,x,0); 20 end; 21 function bfs:boolean; 22 var i,x,y:longint; 23 begin 24 fillchar(h,sizeof(h),0); 25 l:=0;r:=1;q[1]:=s;h[s]:=1; 26 while l<r do 27 begin 28 inc(l); 29 x:=q[l]; 30 i:=head[x]; 31 while i<>0 do 32 begin 33 y:=e[i].go; 34 if (e[i].v<>0) and (h[y]=0) then 35 begin 36 h[y]:=h[x]+1; 37 inc(r);q[r]:=y; 38 end; 39 i:=e[i].next; 40 end; 41 end; 42 exit (h[t]<>0); 43 end; 44 function dfs(x,f:longint):longint; 45 var i,y,used,tmp:longint; 46 begin 47 if x=t then exit(f); 48 used:=0; 49 i:=cur[x]; 50 while i<>0 do 51 begin 52 y:=e[i].go; 53 if (h[y]=h[x]+1) and (e[i].v<>0) then 54 begin 55 tmp:=dfs(y,min(e[i].v,f-used)); 56 dec(e[i].v,tmp);if e[i].v<>0 then cur[x]:=i; 57 inc(e[i xor 1].v,tmp); 58 inc(used,tmp); 59 if used=f then exit(f); 60 end; 61 i:=e[i].next; 62 end; 63 if used=0 then h[x]:=-1; 64 exit(used); 65 end; 66 procedure dinic; 67 begin 68 while bfs do 69 begin 70 for i:=s to t do cur[i]:=head[i]; 71 inc(maxflow,dfs(s,inf)); 72 end; 73 end; 74 procedure init; 75 begin 76 tot:=1; 77 readln(n,m); 78 s:=0;t:=n+1; 79 for i:=1 to n do 80 begin 81 read(x); 82 if x=0 then insert(s,i,1) 83 else insert(i,t,1); 84 end; 85 readln; 86 for i:=1 to m do begin readln(x,y);insert(x,y,1);insert(y,x,1);end; 87 end; 88 procedure main; 89 begin 90 maxflow:=0; 91 dinic; 92 writeln(maxflow); 93 end; 94 begin 95 assign(input,‘input.txt‘);assign(output,‘output.txt‘); 96 reset(input);rewrite(output); 97 init; 98 main; 99 close(input);close(output);100 end.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。