网络流例题选讲

之前的文章曾经讲解过网络流与费用流的各种算法,今天在这里总结一些最近做的好题。

网络流例题选讲

第一题倒是自己想出来了,第二题……结合了三个人的力量,才勉强拼凑出正解……还是比较有思维难度的。

BZOJ1934[SHOI2007] 善意的投票

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1934

题意

幼儿园里有$n$个小朋友打算通过投票来决定睡不睡午觉。对他们来说,这个问题并不是很重要,于是他们决定发扬谦让精神。虽然每个人都有自己的主见,但是为了照顾一下自己朋友的想法,他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。 我们的问题就是,每位小朋友应该怎样投票,才能使冲突数最小?
第一行只有两个整数$n$,$m$,保证有$2 \leqslant n \leqslant 300$,$1 \leqslant m \leqslant \frac{n(n-1)}{2}$。其中$n$代表总人数,$m$代表好朋友的对数。文件第二行有$n$个整数,第$i$个整数代表第$i$个小朋友的意愿,当它为$1$时表示同意睡觉,当它为$0$时表示反对睡觉。接下来文件还有$m$行,每行有两个整数$i$,$j$。表示$i$,$j$是一对好朋友,我们保证任何两对$i$,$j$不会重复。

题解

对于这一类的模型(即对每个点都有两种值,求出某一特定的式子),我们都可以考虑最小割的模型:每个点与源汇点分别连一条边,割掉这条边分别表示两种取值,再根据题目的要求,在各点之间连边即可。比如说对这一道题,我们可以把每个点与源点和汇点分别连边。割掉与源点之间的边表示反对睡觉,否则表示同意睡觉。对于朋友之间得冲突,只需在每对朋友之间连一条边权为$1$的边即可。然后一遍最小割,问题解决。
时间复杂度$O(maxflow(n,m))$。

代码

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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxn=3e2+10;
const int maxm=2e5+10;
int to[maxm],nex[maxm],beg[maxn],gap[maxn],dis[maxn],a[maxn],flow[maxm];
int e=1,n,m,s,t;
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
inline void add(int x,int y,int z){
to[++e]=y;nex[e]=beg[x];beg[x]=e;flow[e]=z;
swap(x,y);
to[++e]=y;nex[e]=beg[x];beg[x]=e;flow[e]=0;
}
int Isap(int x,ll f){
if(x==t)return f;
int res=f,i;
for(i=beg[x];i;i=nex[i])
if(flow[i]>0 && dis[x]==dis[to[i]]+1){
int minflow=Isap(to[i],min(res,flow[i]));
flow[i]-=minflow;
flow[i^1]+=minflow;
res-=minflow;
if(!res)return f;
}
if(!(--gap[dis[x]]))dis[s]=t;
gap[++dis[x]]++;
return f-res;
}
int main(){
int i,j,k,T;
#ifndef ONLINE_JUDGE
freopen("BZOJ1934.in","r",stdin);
freopen("BZOJ1934.out","w",stdout);
#endif
n=read();m=read();
for(i=1;i<=n;i++){
a[i]=read();
add(n+1,i,a[i]);
add(i,n+2,a[i]^1);
}
for(i=1;i<=m;i++){
int x,y;
x=read();y=read();
add(x,y,1);add(y,x,1);
}
s=n+1;t=n+2;
int maxflow=0;
for(gap[0]=t;dis[s]<t;)maxflow+=Isap(s,1e9);
printf("%d\n",maxflow);
return 0;
}

BZOJ2756[SCOI2012] 奇怪的游戏

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2756

题意

Blinker最近喜欢上一个奇怪的游戏。
这个游戏在一个$n \times m$的棋盘上玩,每个格子有一个数。每次Blinker会选择两个相邻的格子,并使这两个数都加上$1$。
现在Blinker想知道最少多少次能使棋盘上的数都变成同一个数,如果永远不能变成同
一个数则输出$-1$。
$1 \leqslant T \leqslant 10,1 \leqslant n,m \leqslant 40$。

题解

考虑对棋盘黑白染色,不难发现,每次对相邻的点对加$1$,都对黑色与白色的点都加了$1$。因此黑色格子的数之和与白色格子的数之和的差是不会变的。设黑色格子上的数之和为$sumb$,白色格子为$sumw$,共进行了$x$次操作,就会有这样一个式子:
$$\frac{sumb+x}{numb}=\frac{sumw+x}{numw}$$
如果$n,m$均为奇数,则黑色格子会比白色格子多一个。那么$x$就会有唯一解了,只需check一下就可以了。
如果$nm \equiv 0(mod 2)$,那么$numb=numw$。如果$sumb \not= sumw$,就可以输出$-1$,否则原方程就会有无穷多组解了。这个时候,我们注意到,若$x$是可行解,那么$x+\frac{nm}{2}$也会是一组可行解。所以可以二分一下最后每个格子里的数,再check一下就可以了。
check函数则要用网络流来处理。设$t$为最终每个格子里的数,将每个黑色格子与源点连一条流量为$t-a[i][j]$的边,相邻的格子之间连一条流量为$INF$的边,白色格子与汇点连一条流量为$t-a[i][j]$的边。check一下是否满流即可。
时间复杂度$O(maxflow(n \times m,n \times m)logINF)$。
这道题我和dyx,zhou888一起看了好久,最后我想到了前面的染色分类,dyx想到了二分格子里的数,zhou888想到了网络流的建模(orz),三个人勉强把正解凑了出来……

代码

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll INF=1e18;
const long double eps=1e-9;
const int maxsz=40+10;
const int maxn=2e3+10;
const int maxm=2e4+10;
int to[maxm],nex[maxm],beg[maxn],gap[maxn],dis[maxn],a[maxsz][maxsz];
ll flow[maxm];
int e=1,n,m,s,t;
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
inline void Cls(){
e=1;
memset(beg,0,sizeof(beg));
memset(gap,0,sizeof(gap));
memset(dis,0,sizeof(dis));
}
inline void add(int x,int y,ll z){
to[++e]=y;nex[e]=beg[x];beg[x]=e;flow[e]=z;
swap(x,y);
to[++e]=y;nex[e]=beg[x];beg[x]=e;flow[e]=0;
}
ll Isap(int x,ll f){
if(x==t)return f;
ll res=f,i;
for(i=beg[x];i;i=nex[i])
if(flow[i]>0 && dis[x]==dis[to[i]]+1){
ll minflow=Isap(to[i],min(res,flow[i]));
flow[i]-=minflow;
flow[i^1]+=minflow;
res-=minflow;
if(!res)return f;
}
if(!(--gap[dis[x]]))dis[s]=t;
gap[++dis[x]]++;
return f-res;
}
inline int check(ll val){
int i,j;
ll tot=0;
Cls();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
if((i+j)%2==1){
add(n*m+1,(i-1)*m+j,val-a[i][j]),tot+=val-a[i][j];
if(i>1)add((i-1)*m+j,(i-2)*m+j,INF);
if(j>1)add((i-1)*m+j,(i-1)*m+j-1,INF);
if(i<n)add((i-1)*m+j,i*m+j,INF);
if(j<m)add((i-1)*m+j,(i-1)*m+j+1,INF);
}
else add((i-1)*m+j,n*m+2,val-a[i][j]);
}
s=n*m+1;t=n*m+2;
ll maxflow=0;
for(gap[0]=t;dis[s]<t;)maxflow+=Isap(s,INF);
return maxflow==tot;
}
int main(){
int i,j,k,T;
#ifndef ONLINE_JUDGE
freopen("BZOJ2756.in","r",stdin);
freopen("BZOJ2756.out","w",stdout);
#endif
T=read();
while(T--){
Cls();
n=read();m=read();
ll sum1=0,sum2=0,maxa=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
a[i][j]=read();
maxa=max(maxa,1ll*a[i][j]);
if((i+j)%2==1)sum1+=1ll*a[i][j];
if((i+j)%2==0)sum2+=1ll*a[i][j];
}
if(n%2==0 || m%2==0){
if(sum1!=sum2){
puts("-1");
continue;
}
ll l=maxa,r=INF;
while(l<r){
ll mid=(l+r)>>1;
if(check(mid))r=mid;
else l=mid+1;
}
printf("%lld\n",(l*n*m-sum1-sum2)/2);
}
if(n%2==1 && m%2==1){
ll delta=sum2*(n*m/2)-sum1*(n*m/2+1);
ll x=(delta*2+sum1+sum2)/(n*m);
if(delta<0 || (delta*2+sum1+sum2)%(n*m)!=0 || !check(x)){
puts("-1");
continue;
}
printf("%lld\n",delta);
}
}
return 0;
}

总结

据zhou888大佬说

那些你做不太出来的,要建模的东西,数据范围又比较小的,那就肯定是网络流了。

所以……以后也许可以这么想一想?
网络流的各种神级建模似乎还是比较多的……目前题做的太少了,建模能力比较菜,就是知道正解是网络流,似乎也想不出。最近还考了一个和第一道题类似的建模方式,但要比它复杂很多的一道题,受启发很大,忽然有种“网络流还可以这么玩”的感觉。
最近要做的题挺多的,网络流暂时先放下了,以后还有时间再来填一些好题进来。