C++之路进阶——bzoj1934(善意的投票)
2024-08-29 09:37:32
F.A.Qs | Home | Discuss | ProblemSet | Status | Ranklist | Contest | ModifyUser hyxzc | Logout | 捐赠本站 |
---|
Notice:由于本OJ建立在Linux平台下,而许多题的数据在Windows下制作,请注意输入、输出语句及数据类型及范围,避免无谓的RE出现。
1934: [Shoi2007]Vote 善意的投票
Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 1646 Solved: 1006
[Submit][Status][Discuss]
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
在第一个例子中,所有小朋友都投赞成票就能得到最优解
题解:
将点与S、T点分别连边,权值为1或0,将路径连边,最大流
代码:
#include<cstdio>
#include<queue>
#include<cstring>
#define maxn 310
#include<iostream> using namespace std; int S=,T,head[maxn],dis[maxn],maxlow,ans,cnt=,n,m,x[maxn];
struct ss
{
int to;
int next;
int edge;
}e[]; void add(int u,int v,int w)
{
e[++cnt].next=head[u];
head[u]=cnt;
e[cnt].to=v;
e[cnt].edge=w;
} void insert(int u,int v,int w)
{
add(u,v,w);
add(v,u,);
} bool bfs()
{
for (int i=;i<=T;i++) dis[i]=0x7fffffff;
queue<int>que;
que.push(S);
dis[]=;
while (!que.empty())
{
int now=que.front();
que.pop();
for (int i=head[now];i;i=e[i].next)
if (e[i].edge&&dis[e[i].to]>dis[now]+)
{
dis[e[i].to]=dis[now]+;
que.push(e[i].to);
if (e[i].to==T) return ;
}
}
return ;
} int dinic(int x,int inf)
{
if (x==T) return inf;
int rest=inf;
for (int i=head[x];i&&rest;i=e[i].next)
if (e[i].edge&&dis[e[i].to]==dis[x]+)
{
int now=dinic(e[i].to,min(rest,e[i].edge));
if (!now) dis[now]=;
e[i].edge-=now;
e[i^].edge+=now;
rest-=now;
}
return inf-rest;
} int main()
{
scanf("%d%d",&n,&m);
T=n+;
for (int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
if (x)
insert(,i,),insert(i,T,);
else
insert(i,T,),insert(,i,);
}
for (int i=;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
insert(u,v,);
insert(v,u,);
}
while (bfs())
while (ans=dinic(S,0x7fffffff)) maxlow+=ans;
printf("%d\n",maxlow);
return ;
}
最新文章
- parted LVM划分4T磁盘,在线扩展1.5T
- 前台json 的一些 处理 (转)
- ZeroMQ接口函数之 :zmq_proxy_steerable – 以STOP/RESUME/TERMINATE控制方式开启内置的ZMQ代理
- linux中的内存申请函数的区别 kmalloc, vmalloc
- Servlet学习之web服务器Tomcat 详解
- [LintCode] Wiggle Sort II 扭动排序之二
- Win10如何设置防火墙开放特定端口 windows10防火墙设置对特定端口开放的方法
- 为什么C++类定义中,数据成员不能被指定为自身类型,但可以是指向自身类型的指针或引用?为什么在类体内可以定义将静态成员声明为其所属类的类型呢 ?
- 数据校验validator 与 DWZ
- AbstractExecutorService (未完成)
- NetBeans中文乱码解决办法
- Div 3 - SGU 105(找规律)
- poj 2245 Lotto(dfs)
- 将string当字节流使
- 如何使用angularJs
- c语言程序设计第3周编程作业(数字特征)
- gem devise配置
- javascript随机一个1-9的数字
- Servlet 单例多线程【转】
- fasthttp 文档手册
热门文章
- 再过几个月Apple Watch就要正式发布了
- Infragistics公司的UltraWebGrid控件在显示的时候报“theForm” 未定义错误的解决。
- C#中如何在字符串中设置上标
- AJAX.JSONP 跨域
- osg中使用MatrixTransform来实现模型的平移/旋转/缩放
- C#读取文本播放相应语音【转】
- 1055. The World&#39;s Richest (25)
- css3常用代码整理
- HDU3732 背包DP
- 理解group by 语句的扩展使用