B1934 [Shoi2007]Vote 善意的投票 最小割
2024-09-07 12:56:16
一开始不太会,结果看完题解就是一个建图的网络流。然后就结了。
题干:
题目描述 幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说,这个问题并不是很重要,于是他们决定发扬谦让精神。虽然每个人都有自己的主见,但是为了照顾一下自己朋友的想法,他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。 我们的问题就是,每位小朋友应该怎样投票,才能使冲突数最小? 输入输出格式 输入格式:
文件的第一行只有两个整数n,m,保证有2≤n≤,≤m≤n(n-)/。其中n代表总人数,m代表好朋友的对数。文件第二行有n个整数,第i个整数代表第i个小朋友的意愿,当它为1时表示同意睡觉,当它为0时表示反对睡觉。接下来文件还有m行,每行有两个整数i,j。表示i,j是一对好朋友,我们保证任何两对i,j不会重复。 输出格式:
只需要输出一个整数,即可能的最小冲突数。 输入输出样例 输入样例#: 复制 输出样例#: 复制 说明 ≤n≤,≤m≤n(n-)/。
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
#define duke(i,a,n) for(int i = a;i <= n;i++)
#define inf 99999999
template <class T>
void read(T &x)
{
char c;
bool op = ;
while(c = getchar(),c > '' || c < '')
if(c == '-') op = ;
x = c - '';
while(c = getchar(),c >= '' && c <= '')
x = x * + c - '';
if(op == )
x = -x;
}
struct node{
int x,y,c,nxt,other;
};
node a[];
int len = ,last[],st,ed;
int list[];
void add(int x,int y,int w)
{
int k1,k2;
a[++len].nxt = last[x];
k1 = len;
a[len].x = x;
a[len].y = y;
a[len].c = w;
last[x] = len;
a[++len].nxt = last[y];
k2 = len;
a[len].x = y;
a[len].y = x;
a[len].c = w;
last[y] = len;
a[k1].other = k2;
a[k2].other = k1;
}
int h[];
bool bfs()
{
memset(h,,sizeof(h));
h[st] = ;
int head,tail;
list[] = st;
head = ;
tail = ;
while(head != tail)
{
int x = list[head];
for(int k = last[x];k;k = a[k].nxt)
{
int y = a[k].y;
if(a[k].c > && h[y] == )
{
h[y] = h[x] + ;
list[tail++] = y;
}
}
head++;
}
if(h[ed] > )
return true;
else
return false;
}
int find(int x,int f)
{
if(x == ed)
{
return f;
}
int s = ,t;
for(int k = last[x];k;k = a[k].nxt)
{
int y = a[k].y;
if(s < f && h[y] == (h[x] + ) && a[k].c > )
{
t = find(y,min(a[k].c,f - s));
s += t;
a[k].c -= t;
a[a[k].other].c += t;
}
}
if(s == )
h[x] = ;
return s;
}
int n,m;
int main()
{
read(n);read(m);
int x,y;
st = ;
ed = ;
duke(i,,n)
{
read(x);
if(x == )
{
add(st,i,);
}
else
{
add(i,ed,);
}
}
duke(i,,m)
{
read(x);read(y);
add(x,y,);
}
int tot = ;
while(bfs())
{
tot += find(st,inf);
}
printf("%d",tot);
return ;
}
最新文章
- ubuntu 好玩多了
- 百度地图api(摘自百度)
- ifram,framset 互相调用JS
- erl0010 - erlang查看ets 当前系统使用情况和当前配置上限
- 关闭VS时, 每次都 会弹出 保存以下各项的更改吗?
- groovy --不注意的小错误(java.lang.String.positive() is applicable)
- forever 使用
- JS 在html中的位置
- 关于block 用法
- memcached 第二篇----安装使用
- 【JAVAWEB学习笔记】12_Http&;Tomcat
- java如何声明一个数组用来存储随机生成的字母并且保证不重复
- SparkSQL——用之惜之
- 或许,挂掉的点总是出人意料(hw其实蛮有好感的公司)
- 第六节:深入研究Task实例方法ContinueWith的参数TaskContinuationOptions
- linux netcat 命令详解
- mybatis的collection查询问题以及使用原生解决方案的结果
- HDOJ 3308 LCIS (线段树)
- Apache系列:Centos7.2下安装与配置apache
- 在android 上 使用 rxjava 入门篇