最小割相关问题

发表于 | 分类于 | 阅读次数:
最小割模型很经典了，本文主要举例说明最小割的建图方法和最小割的一些性质。

#最小割建图

二分图

某些问题可以转化为二分图模型，就是某些元素选或不选，然后有某些条件，这类题目直接建就好。

[SHOI2007] Vote 善意的投票

[JLOI2010] 冠军调查

上面两道是裸题。

当然也有些题目需要考虑如何建成二分图，关键就是确定某一划分标准。

例如：

###千钧一发 aka. Number

给定 $n$ 个正整数，需要从中选出一些数，使这些数的和（或者权值）最大。

若两个数 $a,b$ 同时满足以下条件，则 $a,b$ 不能同时被选

  1. 存在正整数 $c$ ，使 $a^2+b^2=c^2$
  2. $\gcd(a,b)=1$

$n\leq3000$

这两道题目乍一看是十分典型的最大团问题的变种，一般化之后属于 NPC ，然而给出的冲突条件很特殊，可以发现，两个偶数一定不满足条件 2 , 而连个奇数一定不满足条件 1 . 于是可以建成二分图跑最小割。

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
/**************************************************************
    Problem: 3158
    User: zhangche0526
    Language: C++
    Result: Accepted
    Time:208 ms
    Memory:27108 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
using std::floor;
using std::min;
typedef long long ll;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
const int MAXN=1e3+100,MAXM=1e6+1e5,INF=1061109567;
 
int S,T;
 
struct E{int next,to,cap;} e[MAXM<<1];int ecnt=1,G[MAXN];
void addEdge(int u,int v,int c)
{   
    e[++ecnt]=(E){G[u],v,c};G[u]=ecnt;
    e[++ecnt]=(E){G[v],u,0};G[v]=ecnt;
}
 
std::queue<int> que;
int dpt[MAXN];
bool calDpt()
{
    memset(dpt,-1,sizeof dpt);
    que.push(S);dpt[S]=0;
    while(!que.empty())
    {
        int u=que.front();que.pop();
        for(int i=G[u];i;i=e[i].next) if(e[i].cap>0)
        {
            int v=e[i].to;
            if(~dpt[v]) continue;
            dpt[v]=dpt[u]+1;
            que.push(v);
        }
    }
    return ~dpt[T];
}
 
int iter[MAXN];
int calF(int u,int f)
{
    if(u==T) return f;
    for(int &i=iter[u];i;i=e[i].next) if(e[i].cap>0)
    {
        int v=e[i].to;
        if(dpt[v]!=dpt[u]+1) continue;
        int res=calF(v,min(f,e[i].cap));
        if(res>0)
        {
            e[i].cap-=res,e[i^1].cap+=res;
            return res;
        }
    }
    return 0;
}
 
int maxFlow()
{
    int f,res=0;
    while(calDpt())
    {
        memcpy(iter,G,sizeof G);
        while(f=calF(S,INF)) res+=f;
    }
    return res;
}
 
 
int n;
int A[MAXN],B[MAXN];
inline bool jud(int i,int j)
{
    double SAA=sqrt((ll)A[i]*A[i]+(ll)A[j]*A[j]);
    if(floor(SAA)!=SAA) return true;
    if(gcd(A[i],A[j])>1) return true;
    return false;
}
inline void buildGraph()
{
    int i,j;S=n+1,T=n+2;
    for(i=1;i<=n;i++)
        if(A[i]&1) addEdge(S,i,B[i]);
        else addEdge(i,T,B[i]);
    for(i=1;i<=n;i++) if(A[i]&1)
        for(j=1;j<=n;j++) if(!(A[j]&1))
            if(!jud(i,j)) addEdge(i,j,INF);
}
int main()
{
    int i,ans=0;scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d",A+i);
    for(i=1;i<=n;i++) scanf("%d",B+i),ans+=B[i];
    buildGraph();
    ans-=maxFlow();
    printf("%d",ans);
    return 0;
}

点权转化为边权

有些问题要割掉的是点，这时我们将点拆成两个，入边连一个点，出边连另一个点，两点之间的边权赋为点权，其它边赋为 $\infty$ .

[Baltic2008]Mafia

匪徒准备从一个车站转移毒品到另一个车站，警方准备进行布控。对于每个车站进行布控都需要一定的代价，现在警方希望使用最小的代价控制一些车站,使得去掉这些车站后，匪徒无法从原定的初始点到达目标点。

$n\leq200,m\leq2\times10^4$

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using std::min;

const int MAXV=500,MAXE=6e4,INF=1061109567;

int S,T;

struct E{int next,to,cap;} e[MAXE<<1];int ecnt=1,G[MAXV];
void addEdge(int u,int v,int c)
{
	e[++ecnt]=(E){G[u],v,c};G[u]=ecnt;
	e[++ecnt]=(E){G[v],u,0};G[v]=ecnt;
}

std::queue<int> que;
int dpt[MAXV];
bool calDpt()
{
	memset(dpt,-1,sizeof dpt);
	dpt[S]=0;que.push(S);
	while(!que.empty())
	{
		int u=que.front();que.pop();
		for(int i=G[u];i;i=e[i].next) if(e[i].cap>0)
		{
			int v=e[i].to;
			if(~dpt[v]) continue;
			dpt[v]=dpt[u]+1;
			que.push(v);
		}
	}
	return ~dpt[T];
}

int iter[MAXV];
int calF(int u,int f)
{
	if(u==T) return f;
	for(int &i=iter[u];i;i=e[i].next) if(e[i].cap>0)
	{
		int v=e[i].to;
		if(dpt[v]!=dpt[u]+1) continue;
		int res=calF(v,min(f,e[i].cap));
		if(res>0)
		{
			e[i].cap-=res,e[i^1].cap+=res;
			return res;
		}
	}
	return 0;
}

int maxFlow()
{
	int f,res=0;
	while(calDpt())
	{
		memcpy(iter,G,sizeof G);
		while(f=calF(S,INF)) res+=f;
	}
	return res;
}

int n,m,s,t;

int main()
{
	int i,w;scanf("%d%d%d%d",&n,&m,&s,&t);
	S=n+1<<1,T=S+1;addEdge(S,s<<1,INF);addEdge(t<<1|1,T,INF);
	for(i=1;i<=n;i++){scanf("%d",&w);addEdge(i<<1,i<<1|1,w);}
	for(i=1;i<=m;i++)
	{
		int u,v;scanf("%d%d",&u,&v);
		addEdge(u<<1|1,v<<1,INF);
		addEdge(v<<1|1,u<<1,INF);
	}
	printf("%d",maxFlow());
	return 0;
}

#最小割的性质

##充分条件&必要条件

最小割的题目大都关注整体，但是当我们关注某一条边的时候就有了一个很有意思的问题：一条边是最小割中的边的充分条件和必要条件是什么？

首先分析一下性质，注意到残余网络中的源汇一定不属于同一强连通分量（不然可以继续增广），于是残余网络中得到点就可以分为三类：

  1. 在源点的强连通分量中；
  2. 在汇点的强连通分量中；
  3. 其它

这个问题十分经典，前辈早已研究过并总结出以下定理：

  • 一条边在最小割中的必要条件 是 它的两个节点在残余网络中不属于同一强连通分量。
  • 一条边在最小割中的充分条件 是 它的两个节点在残余网络中分别于源点和汇点属于同一强连通分量。

第一条根据定义显然成立。

对于第二条：一条边的两点若是分属源汇的强连通分量中，则此边权增大，最小割一定增大；也就是说，这样的边一定属与割边。

###[AHOI2009] 最小割 Mincut

给定一张 $n$ 个点 $m$ 条边的有向带权图，问每一条边可不可以、一不一定属于最小割。

$n\leq4000,m\leq6\times10^4$

用 Tarjan 求出强连通分量后应用上述定理。

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
113
114
115
116
117
118
119
120
121
122
123
124
/**************************************************************
    Problem: 1797
    User: zhangche0526
    Language: C++
    Result: Accepted
    Time:320 ms
    Memory:3264 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<cstring>
using std::min;
inline void umn(int &a,int b){a=min(a,b);}
 
const int MAXN=4e3+5,MAXM=6e4+5,INF=1061109567;
 
int N,M,S,T;
 
struct E{int next,fr,to,cap;} e[MAXM<<1];int ecnt=1,G[MAXN];
void addEdge(int u,int v,int c)
{
    e[++ecnt]=(E){G[u],u,v,c};G[u]=ecnt;
    e[++ecnt]=(E){G[v],v,u,0};G[v]=ecnt;
}
 
std::queue<int> que;
int dpt[MAXN];
bool calDpt()
{
    memset(dpt,-1,sizeof dpt);
    que.push(S);dpt[S]=0;
    while(!que.empty())
    {
        int u=que.front();que.pop();
        for(int i=G[u];i;i=e[i].next) if(e[i].cap>0)
        {
            int v=e[i].to;
            if(~dpt[v]) continue;
            dpt[v]=dpt[u]+1;
            que.push(v);
        }
    }
    return ~dpt[T];
}
 
int iter[MAXN];
int calF(int u,int f)
{
    if(u==T) return f;
    for(int &i=iter[u];i;i=e[i].next) if(e[i].cap>0)
    {
        int v=e[i].to;
        if(dpt[v]!=dpt[u]+1) continue;
        int res=calF(v,min(f,e[i].cap));
        if(res>0)
        {
            e[i].cap-=res,e[i^1].cap+=res;
            return res;
        }
    }
    return 0;
}
 
void maxFlow()
{
    int f;
    while(calDpt())
    {
        memcpy(iter,G,sizeof G);
        while(f=calF(S,INF));
    }
}
 
int dfn[MAXN],dcnt,low[MAXN];
std::stack<int> st;bool inSt[MAXN];
int gr[MAXN],gcnt;
void tarjan(int u)
{
    dfn[u]=low[u]=++dcnt;
    st.push(u);inSt[u]=true;
    for(int i=G[u];i;i=e[i].next) if(e[i].cap>0)
    {
        int v=e[i].to;
        if(!dfn[v])
        {
            tarjan(v);
            umn(low[u],low[v]);
        }else if(inSt[v]) umn(low[u],dfn[v]);
    }
    if(low[u]==dfn[u])
    {
        int t;gcnt++;
        do
        {
            t=st.top();st.pop();
            inSt[t]=false;
            gr[t]=gcnt;
        }while(t!=u);
    }
}
 
int main()
{
    int i;
    scanf("%d%d%d%d",&N,&M,&S,&T);
    for(i=1;i<=M;i++)
    {
        int u,v,c;scanf("%d%d%d",&u,&v,&c);
        addEdge(u,v,c);
    }
    maxFlow();
    for(i=1;i<=N;i++) if(!dfn[i]) tarjan(i);
    for(i=2;i<=ecnt;i+=2)
        if(!e[i].cap&&gr[e[i].fr]!=gr[e[i].to])
        {
            if(gr[e[i].fr]==gr[S]&&gr[e[i].to]==gr[T])
                puts("1 1");
            else puts("1 0");
        }else puts("0 0");
    return 0;
}

与生成树性质结合

我们知道一条边在属于最小（大）生成树的必要条件是所有比它权值小（大）的边不能使图连通，充分条件是除它之外所有权值小（大）于等于它的边不能使图连通。容易发现生成树与最小割的性质有一定联系，于是可以利用这些联系处理一些问题。

[Shoi2010] 最小生成树

给定一张 $n$ 个点 $m$ 条边的无向连通图，每次操作时可以将除了某一边的所有边的权值减一，求使得指定边一定属于图的最小生成树的最小操作次数。

$n\leq500,m\leq800$

由于最小生成树的边集只与边的相对权值有关，所以将除了某一边的所有边的权值减一等价于将某一边的权值加一。于是问题就变成了在某些边上加上一定权值使得所有边权不大于指定边的权值的边不能使图连通。

可以将每条边权不大于指定边的权值的边的流量赋为其权值与指定边的权值之差加一，那么以指定边的两端点为源汇的最小割即为答案。

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
/**************************************************************
    Problem: 2521
    User: zhangche0526
    Language: C++
    Result: Accepted
    Time:28 ms
    Memory:1340 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using std::min;
 
const int MAXN=505,MAXM=1605,INF=1061109567;
 
int S,T;
 
struct E{int next,to,cap;} e[MAXM<<1];int ecnt=1,G[MAXN];
void addEdge(int u,int v,int c)
{
    e[++ecnt]=(E){G[u],v,c};G[u]=ecnt;
    e[++ecnt]=(E){G[v],u,0};G[v]=ecnt;
}
void addEdge2(int u,int v,int c){addEdge(u,v,c);addEdge(v,u,c);}
 
std::queue<int> que;
int dpt[MAXN];
bool calDpt()
{
    memset(dpt,-1,sizeof dpt);
    que.push(S);dpt[S]=0;
    while(!que.empty())
    {
        int u=que.front();que.pop();
        for(int i=G[u];i;i=e[i].next) if(e[i].cap>0)
        {
            int v=e[i].to;
            if(~dpt[v]) continue;
            dpt[v]=dpt[u]+1;
            que.push(v);
        }
    }
    return ~dpt[T];
}
 
int iter[MAXN];
int calF(int u,int f)
{
    if(u==T) return f;
    for(int &i=iter[u];i;i=e[i].next) if(e[i].cap>0)
    {
        int v=e[i].to;
        if(dpt[v]!=dpt[u]+1) continue;
        int res=calF(v,min(f,e[i].cap));
        if(res>0)
        {
            e[i].cap-=res,e[i^1].cap+=res;
            return res;
        }
    }
    return 0;
}
 
int maxFlow()
{
    int f,res=0;
    while(calDpt())
    {
        memcpy(iter,G,sizeof G);
        while(f=calF(S,INF)) res+=f;
    }
    return res;
}
 
 
int N,M,L;
 
struct A{int u,v,w;} a[MAXN];
int main()
{
    int i;scanf("%d%d%d",&N,&M,&L);
    for(i=1;i<=M;i++) scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
    S=a[L].u,T=a[L].v;
    for(i=1;i<=M;i++) if(a[i].w<=a[L].w&&i!=L)
        addEdge2(a[i].u,a[i].v,a[L].w-a[i].w+1);
    printf("%d",maxFlow());
    return 0;
}

最小割树

注意：本节只讨论无向图。

最小割树又是一个听起来很神，其实十分 naive 的东西。

主要用来解决多点对之间的最小割问题，有些题目会给出一张 $n$ 个点的无向图，询问所有每两个点之间的最小割。

容易证明 $n$ 个点的无向图的最小割取值只有 $n-1$ 种，而直接暴力求需要跑 $O(n^2)$ 次最小割。

分析复杂度高的原因是我们没有充分利用信息，记 $S$ 集合为残余网络中源点可达的点集， $T$ 同理，那么我们没跑完一次最小割后，$(u,v),u\in S,v\in T$ 的最小割就是确定的了，因此我们只需要分治计算，即每次求最小割后递归处理 $S,T$ 集合，就可以在 $O(n\mathit{maxFlow}(n,m))$ 的时间复杂度内求出所有点对的最小割了，由于分治的过程与二叉树类似，故称“最小割树”。

[Zjoi2011]最小割

给定一张 $n$ 个点 $m$ 条边的无向带权图， $q$ 次询问，每次询问最小割不超过 $x$ 的点对个数。

$T\leq30,n\leq150,m\leq3000,q\leq30$

求出所有点对的最小割，排序，二分。

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
/**************************************************************
    Problem: 2229
    User: zhangche0526
    Language: C++
    Result: Accepted
    Time:1900 ms
    Memory:1556 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using std::min;
inline void umn(int &a,int b){a=min(a,b);}
 
const int MAXN=155,MAXM=3005,INF=1061109567;
 
int S,T;
 
struct E{int next,to,cap;} e[MAXM<<1];int ecnt,G[MAXN];
void addEdge(int u,int v,int c)
{
    e[++ecnt]=(E){G[u],v,c};G[u]=ecnt;
    e[++ecnt]=(E){G[v],u,c};G[v]=ecnt;
}
 
std::queue<int> que;
int dpt[MAXN];
bool calDpt()
{
    memset(dpt,-1,sizeof dpt);
    que.push(S);dpt[S]=0;
    while(!que.empty())
    {
        int u=que.front();que.pop();
        for(int i=G[u];i;i=e[i].next) if(e[i].cap>0)
        {
            int v=e[i].to;
            if(~dpt[v]) continue;
            dpt[v]=dpt[u]+1;
            que.push(v);
        }
    }
    return ~dpt[T];
}
 
int iter[MAXN];
int calF(int u,int f)
{
    if(u==T) return f;
    for(int &i=iter[u];i;i=e[i].next) if(e[i].cap>0)
    {
        int v=e[i].to;
        if(dpt[v]!=dpt[u]+1) continue;
        int res=calF(v,min(f,e[i].cap));
        if(res>0)
        {
            e[i].cap-=res,e[i^1].cap+=res;
            return res;
        }
    }
    return 0;
}
 
int maxFlow()
{
    int f,res=0;
    while(calDpt())
    {
        memcpy(iter,G,sizeof G);
        while(f=calF(S,INF)) res+=f;
    }
    return res;
}
 
int N,M,Q;
 
int mnct[MAXN][MAXN];
int seq[MAXN],tmp[MAXN];
int rsp[MAXN*MAXN],rcnt;
 
bool inS[MAXN];
void bfs()
{
    inS[S]=true;que.push(S);
    while(!que.empty())
    {
        int u=que.front();que.pop();
        for(int i=G[u];i;i=e[i].next) if(e[i].cap>0)
        {
            int v=e[i].to;
            if(inS[v]) continue;
            inS[v]=true,que.push(v);
        }
    }
}
 
void dc(int l,int r)
{
    if(l==r) return;
     
    int i,j,p1=l,p2=r;S=seq[l],T=seq[r];
    for(i=2;i<=ecnt;i+=2) e[i].cap=e[i^1].cap=(e[i].cap+e[i^1].cap)>>1;
     
    int mxF=maxFlow();
     
    memset(inS,false,sizeof inS);
    bfs();
     
    for(i=1;i<=N;i++) if(inS[i])
        for(j=1;j<=N;j++) if(!inS[j])
            umn(mnct[i][j],mxF),umn(mnct[j][i],mxF);
 
    for(i=l;i<=r;i++)
        if(inS[seq[i]]) tmp[p1++]=seq[i];
        else tmp[p2--]=seq[i];
    for(i=l;i<=r;i++) seq[i]=tmp[i];
     
    dc(l,p2);dc(p1,r);
}
 
inline void solve()
{
    ecnt=1,memset(G,0,sizeof G);
    memset(mnct,0x3f,sizeof mnct);
 
    int i,j;scanf("%d%d",&N,&M);
 
    for(i=1;i<=N;i++) seq[i]=i;
    for(i=1;i<=M;i++)
    {
        int u,v,c;scanf("%d%d%d",&u,&v,&c);
        addEdge(u,v,c);
    }
 
    dc(1,N);
 
    rcnt=0;
    for(i=1;i<N;i++) for(j=i+1;j<=N;j++)
        rsp[++rcnt]=mnct[i][j];
    std::sort(rsp+1,rsp+rcnt+1);
 
    //for(i=1;i<=rcnt;i++) printf("%d\n",rsp[i]);
 
    scanf("%d",&Q);
    while(Q--)
    {
        int x;scanf("%d",&x);
        int res=std::upper_bound(rsp+1,rsp+rcnt+1,x)-rsp-1;
        printf("%d\n",res);
    }
}
 
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        solve();
        if(T) puts("");
    }
    return 0;
}

[Cqoi2016]不同的最小割

给定一张 $n$ 个点 $m$ 条边的无向带权图，求所有点对间数值不同的最小割的个数。

$n\leq850,m\leq8500$

求出所有点对之间的最小割，排序，去重。

代码与上题一个套路。