1934: [Shoi2007]Vote 善意的投票
Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 1174 Solved: 723
[Submit][Status]
Description
Input
Output
Sample Input
1 0 0
1 2
1 3
3 2
Sample Output
HINT
在第一个例子中,所有小朋友都投赞成票就能得到最优解
Source
/**************************************************************
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 善意的投票的更多相关文章
-
BZOJ 1934: [Shoi2007]Vote 善意的投票 最小割
1934: [Shoi2007]Vote 善意的投票 Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeOnl ...
-
最小投票BZOJ 1934([Shoi2007]Vote 善意的投票-最小割)
上班之余抽点时间出来写写博文,希望对新接触的朋友有帮助.今天在这里和大家一起学习一下最小投票 1934: [Shoi2007]Vote 好心的投票 Time Limit: 1 Sec Memory L ...
-
【BZOJ】1934: [Shoi2007]Vote 善意的投票(网络流/-二分图匹配)
http://www.lydsy.com/JudgeOnline/problem.php?id=1934 一开始我想到了这是求最小割,但是我认为这题二分图可做,将1的放在左边,0的放在右边,然后朋友连 ...
-
BZOJ 1934 [Shoi2007]Vote 善意的投票(最小割)
[题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=1934 [题目大意] 每个人对于投票都有自己原来的观点:1或者0, 他可以违背自己原来的 ...
-
1934: [Shoi2007]Vote 善意的投票 - BZOJ
Description幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉.对他们来说,这个问题并不是很重要,于是他们决定发扬谦让精神.虽然每个人都有自己的主见,但是为了照顾一下自己朋友的想法,他们也可以 ...
-
●BZOJ 1934 [Shoi2007]Vote 善意的投票
题链: http://www.lydsy.com/JudgeOnline/problem.php?id=1934 题解: 题目有点迷. S向为1的点连边,为0的点向T连边,在有关系的两个点之间连双向边 ...
-
【刷题】BZOJ 1934 [Shoi2007]Vote 善意的投票
Description 幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉.对他们来说,这个问题并不是很重要,于是他们决定发扬谦让精神.虽然每个人都有自己的主见,但是为了照顾一下自己朋友的想法,他们也可 ...
-
bzoj 1934: [Shoi2007]Vote 善意的投票
#include<cstdio> #include<iostream> #define M 100000 #include<cstring> using names ...
-
bzoj 1934: [Shoi2007]Vote 善意的投票 (最小割)
原来是赞同的连源,原来是反对的连汇,然后是朋友的就连在一起,这样最小割就是割掉违背和谐的吧 type arr=record toward,next,cap:longint; end; const ma ...
随机推荐
-
c++读书笔记, 零散点滴的收获
1. 字节长度: short <= int <= long <= long long 2. wchar_t,最大扩展字符集合:char16_t.char32_t,unocide字符集 ...
-
SSH和SFTP简介
传统FTP 在传输机制和实现原理上是没有考虑安全机制的,因为它们在网络上用明文传送数据.用户帐号和用户口令,别有用心的人非常容易地就可以截获这些数据.用户帐 号和用户口令.而且,这些网络服务程序容易受 ...
-
ubuntu 15 安装Qt
Linux 下安装 QT5.4.0 http://blog.163.com/xd8171@126/blog/static/620810432015027111314471/ Linux qt ...
-
Oracle利用external table 查看trace文件
1. 用下面的语句找到trace文件的路径 select * from v$diag_info where name='Default Trace File'; 2. 创建一个directory用来加 ...
-
九度 Online Judge 之《剑指 Offer》一书相关题目解答
前段时间准备华为机试,正好之前看了一遍<剑指 Offer>,就在九度 Online Judge 上刷了书中的题目,使用的语言为 C++:只有3题没做,其他的都做了. 正如 Linus To ...
-
去掉firefox点击按钮时的虚线边框
去掉火狐里面点击按钮时候的虚线边框 button::-moz-focus-inner, input[type="reset"]::-moz-focus-inner, input[t ...
-
Dot模板的使用小结2
<!doctype html> <html lang="en"> <head> <meta charset="UTF-8&quo ...
-
Robot Framework + appium 启动手机浏览器的两个方法(1)
一.Open Browser启动 使用Selenium2Library的Open Browser方法,例子如下: browser=手机浏览器类型,如chrome 二.Open Application启 ...
-
Exception in thread ";main"; java.lang.NullPointerException
1.在window操作系统上,使用eclipse开发工具从hdfs分布式文件系统上下载文件报空指针异常解决方法: log4j:WARN No appenders could be found for ...
-
Sitecore CMS中的项目如何配置帮助文本
如何在Sitecore CMS中的项目上配置帮助文本. 所有Sitecore项目都有长短描述字段,以及“帮助链接”字段.这些字段有助于向内容编辑者提供其他信息.这对于很少编辑的项目和字段尤其重要,因为 ...