首页 > 代码库 > BZOJ1934: [Shoi2007]Vote 善意的投票

BZOJ1934: [Shoi2007]Vote 善意的投票

2024-07-17 05:39:06   223人阅读

1934: [Shoi2007]Vote 善意的投票

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 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

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) 冲突是同意与不同意之间的割
代码：
  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.
View Code

 


联系
我们