【Bzoj1934】【Bzoj2768】善意的投票&冠军调查

来源和评测点

这两道题连样例都是一模一样的……下文以1934来分析
Bzoj1934
Bzoj2768

注意!Bzoj2768冠军调查数据可能和题面不同,
网络流边数应开到40万而不是10万

题目

【题目大意】
幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说,这个问题并不是很重要,于是他们决定发扬谦让精神。虽然每个人都有自己的主见,但是为了照顾一下自己朋友的想法,他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。 我们的问题就是,每位小朋友应该怎样投票,才能使冲突数最小?
【输入格式】
第一行只有两个整数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不会重复。
【输出格式】
只需要输出一个整数,即可能的最小冲突数。
【输入样例】
3 3
1 0 0
1 2
1 3
3 2
【输出样例】
1
【样例解释】
所有小朋友都投赞成票就能得到最优解

分析

网络流教程和题目分类参见:
【OI之路】03图论算法-4网络流
其他最小割题目参见:Tag-最小割

考验模型转化能力,难度2吧
想了十多分钟?当然,已经知道是最小割了

“分配方案”、“强制站队”是我自己的理解方式,因人而异吧

一开始想着“分配方案”最大流,每个人与1、0连接,然后后面朋友间的边权依赖于前面,所以不可行

由于只有睡和不睡两种选择,考虑最小割“强制站队”,源点是睡觉的,汇点是不睡觉的
每个人只能选择其中一个,形成了最小割
构图:
依然要拆点
源点到左人、右人到汇点,边权都根据个人意愿决定,是自己意愿就是1,因为拆了就违反意愿,否则为0
同理,好朋友之间边权是1

想想特例:
1、
所有人都不想睡觉,最大流是0
好朋友之间也不会有违背,确实是0,没问题
2、
没有好朋友,最大流是0
直接每个人依照自己意愿,确实是0,也没问题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int mymin(int x,int y) {return x<y?x:y;}
const int MAXN=1000,MAXM=410000;
struct pt
{
int h;
int hou;
}p[MAXN];
struct rod
{
int y,c,g;
int oth;
}e[MAXM];
int ln;
void ins(int x,int y,int c)
{
ln++;
e[ln].y=y;e[ln].c=c;
e[ln].g=p[x].hou;p[x].hou=ln;
ln++;
e[ln].y=x;e[ln].c=0;
e[ln].g=p[y].hou;p[y].hou=ln;
e[ln].oth=ln-1;e[ln-1].oth=ln;
}
int st,ed;
int lst[MAXN];
bool bfs()
{
for(int i=1;i<=ed;i++) p[i].h=0;
lst[1]=st;p[st].h=1;
int tou=1,wei=1;
while(tou<=wei)
{
int x=lst[tou];
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(p[y].h==0 and e[k].c>0)
{
p[y].h=p[x].h+1;
lst[++wei]=y;
}
}
tou++;
}
return p[ed].h>0;
}
int dfs(int x,int f)
{
if(x==ed) return f;
int t=0;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(p[y].h==p[x].h+1 and t<f and e[k].c>0)
{
int tt=dfs(y,mymin(f-t,e[k].c));
t+=tt;e[k].c-=tt;e[e[k].oth].c+=tt;
}
}
if(t==0) p[x].h=0;
return t;
}
int main()
{
int n,m;scanf("%d%d",&n,&m);
st=n+n+1,ed=n+n+2;ln=0;
for(int i=1;i<=n;i++)
{
int t;scanf("%d",&t);
if(t) ins(st,i,1);
else ins(n+i,ed,1);
}
for(int i=1;i<=m;i++)
{
int x,y;scanf("%d%d",&x,&y);
ins(x,n+y,1);ins(y,n+x,1);
}
int ans=0;
while(bfs()) ans+=dfs(st,INF);
printf("%d",ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/a1fb.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%