1934: [Shoi2007]Vote 善意的投票

时间:2022-07-01 00:29:15

1934: [Shoi2007]Vote 善意的投票

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

题解:一道网络流题——将选1的小朋友与源点相连,0的与汇点相连,小朋友之间为朋友的连边,所有边权为1,直接一边sap搞定(PS:网络流题目注意边的方向,切忌把方向弄反!!!)
 /**************************************************************
Problem:
User: HansBug
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ type
point=^node;
node=record
g,w:longint;
next,anti:point;
end;
var
i,j,k,l,m,n,ans,s,t:longint;
a:array[..] of point;
c,d,dv:array[..] of longint;
function min(x,y:longint):longint;inline;
begin
if x<y then min:=x else min:=y;
end;
procedure add(x,y,z:longint);inline;
var p:point;
begin
new(p);p^.g:=y;p^.w:=z;p^.next:=a[x];a[x]:=p;
new(p);p^.g:=x;p^.w:=;p^.next:=a[y];a[y]:=p;
a[x]^.anti:=a[y];a[y]^.anti:=a[x];
end;
function dfs(x,flow:longint):longint;inline;
var i,j,k,l:longint;p:point;
begin
if x=t then exit(flow);
dfs:=;p:=a[x];
while p<>nil do
begin
if (p^.w>) and (d[x]=(d[p^.g]+)) then
begin
k:=dfs(p^.g,min(flow-dfs,p^.w));
dec(p^.w,k);
inc(p^.anti^.w,k);
inc(dfs,k);
if dfs=flow then exit;
end;
p:=p^.next;
end;
if d[s]=n then exit;
dec(dv[d[x]]);
if dv[d[x]]= then d[s]:=n;
inc(d[x]);
inc(dv[d[x]]);
end;
begin
readln(n,m);s:=;t:=n+;
for i:= to n+ do a[i]:=nil;
for i:= to n do
begin
read(c[i]);
if c[i]= then add(,i+,) else add(i+,n+,);
end;
readln;
for i:= to m do
begin
readln(j,k);
if c[j]= then add(j+,k+,) else add(k+,j+,);
end;
n:=n+;
ans:=;
fillchar(d,sizeof(d),);
fillchar(dv,sizeof(dv),);dv[]:=n;
while d[s]<n do inc(ans,dfs(s,maxlongint));
writeln(ans);
readln;
end.

1934: [Shoi2007]Vote 善意的投票的更多相关文章

  1. BZOJ 1934&colon; &lbrack;Shoi2007&rsqb;Vote 善意的投票 最小割

    1934: [Shoi2007]Vote 善意的投票 Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeOnl ...

  2. 最小投票BZOJ 1934&lpar;&lbrack;Shoi2007&rsqb;Vote 善意的投票-最小割&rpar;

    上班之余抽点时间出来写写博文,希望对新接触的朋友有帮助.今天在这里和大家一起学习一下最小投票 1934: [Shoi2007]Vote 好心的投票 Time Limit: 1 Sec Memory L ...

  3. 【BZOJ】1934&colon; &lbrack;Shoi2007&rsqb;Vote 善意的投票(网络流&sol;-二分图匹配)

    http://www.lydsy.com/JudgeOnline/problem.php?id=1934 一开始我想到了这是求最小割,但是我认为这题二分图可做,将1的放在左边,0的放在右边,然后朋友连 ...

  4. BZOJ 1934 &lbrack;Shoi2007&rsqb;Vote 善意的投票(最小割)

    [题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=1934 [题目大意] 每个人对于投票都有自己原来的观点:1或者0, 他可以违背自己原来的 ...

  5. 1934&colon; &lbrack;Shoi2007&rsqb;Vote 善意的投票 - BZOJ

    Description幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉.对他们来说,这个问题并不是很重要,于是他们决定发扬谦让精神.虽然每个人都有自己的主见,但是为了照顾一下自己朋友的想法,他们也可以 ...

  6. ●BZOJ 1934 &lbrack;Shoi2007&rsqb;Vote 善意的投票

    题链: http://www.lydsy.com/JudgeOnline/problem.php?id=1934 题解: 题目有点迷. S向为1的点连边,为0的点向T连边,在有关系的两个点之间连双向边 ...

  7. 【刷题】BZOJ 1934 &lbrack;Shoi2007&rsqb;Vote 善意的投票

    Description 幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉.对他们来说,这个问题并不是很重要,于是他们决定发扬谦让精神.虽然每个人都有自己的主见,但是为了照顾一下自己朋友的想法,他们也可 ...

  8. bzoj 1934&colon; &lbrack;Shoi2007&rsqb;Vote 善意的投票

    #include<cstdio> #include<iostream> #define M 100000 #include<cstring> using names ...

  9. bzoj 1934&colon; &lbrack;Shoi2007&rsqb;Vote 善意的投票 (最小割)

    原来是赞同的连源,原来是反对的连汇,然后是朋友的就连在一起,这样最小割就是割掉违背和谐的吧 type arr=record toward,next,cap:longint; end; const ma ...

随机推荐

  1. c&plus;&plus;读书笔记, 零散点滴的收获

    1. 字节长度: short <= int <= long <= long long 2. wchar_t,最大扩展字符集合:char16_t.char32_t,unocide字符集 ...

  2. SSH和SFTP简介

    传统FTP 在传输机制和实现原理上是没有考虑安全机制的,因为它们在网络上用明文传送数据.用户帐号和用户口令,别有用心的人非常容易地就可以截获这些数据.用户帐 号和用户口令.而且,这些网络服务程序容易受 ...

  3. ubuntu 15 安装Qt

    Linux 下安装 QT5.4.0      http://blog.163.com/xd8171@126/blog/static/620810432015027111314471/ Linux qt ...

  4. Oracle利用external table 查看trace文件

    1. 用下面的语句找到trace文件的路径 select * from v$diag_info where name='Default Trace File'; 2. 创建一个directory用来加 ...

  5. 九度 Online Judge 之《剑指 Offer》一书相关题目解答

    前段时间准备华为机试,正好之前看了一遍<剑指 Offer>,就在九度 Online Judge 上刷了书中的题目,使用的语言为 C++:只有3题没做,其他的都做了. 正如 Linus To ...

  6. 去掉firefox点击按钮时的虚线边框

    去掉火狐里面点击按钮时候的虚线边框 button::-moz-focus-inner, input[type="reset"]::-moz-focus-inner, input[t ...

  7. Dot模板的使用小结2

    <!doctype html> <html lang="en"> <head> <meta charset="UTF-8&quo ...

  8. Robot Framework &plus; appium 启动手机浏览器的两个方法(1)

    一.Open Browser启动 使用Selenium2Library的Open Browser方法,例子如下: browser=手机浏览器类型,如chrome 二.Open Application启 ...

  9. Exception in thread &quot&semi;main&quot&semi; java&period;lang&period;NullPointerException

    1.在window操作系统上,使用eclipse开发工具从hdfs分布式文件系统上下载文件报空指针异常解决方法: log4j:WARN No appenders could be found for ...

  10. Sitecore CMS中的项目如何配置帮助文本

    如何在Sitecore CMS中的项目上配置帮助文本. 所有Sitecore项目都有长短描述字段,以及“帮助链接”字段.这些字段有助于向内容编辑者提供其他信息.这对于很少编辑的项目和字段尤其重要,因为 ...