「Luogu1345」[USACO5.4]奶牛的电信Telecowmunication

problem

Solution

题目要求找到最小数量的若干个点，使得这些点被去掉之后，点c1c_1和c2c_2不连通。

与最小割模型十分类似，考虑转化

约定(u,v,f)(u,v,f)表示uu向vv连边，流量为ff，SS为源，TT为汇

先说模型

对于每个点uu，将其拆成u×2,u×2+1u\times2,u\times2+1两个点，建边(u×2,u×2+1,1)(u\times2,u\times2+1,1)

对于原图上的每条边(u,v)(u,v)，建边(u×2+1,v×2,inf)(u\times2+1,v\times2,inf)

最后令S=c1×2+1,T=c2×2S=c_1\times2+1,T=c_2\times2，求出最小割即可

为什么这样建模？

首先我们割的是点而不是边，我们需要在模型中将这个决策体现出来，因此需要将点拆成一个“入点”和一个“出点”。
去掉每个点对答案的贡献为11，所以入点和出点之间连一条流量为11的边。割掉这条边的意义即为去掉了这个点。

然后对于原图上的无向边，可以视作两条方向相反的有向边
对于每条有向边(u,v)(u,v)，相当于是从uu“出来”，“进入”了vv，所以从uu对应的出点向vv对应的入点连边，流量为正无穷

由于我们是从c1c_1出发到达c2c_2，所以源是c1c_1对应的出点，汇是c2c_2对应的入点

显然最小割一定只包括流量为11的边

Code

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
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define i(u) ((u)<<1)//入
#define o(u) (((u)<<1)|1)//出
using namespace std;
typedef long long ll;

template <typename T> void read(T &t)
{
	t=0;int f=0;char c=getchar();
	while(!isdigit(c)){f|=c=='-';c=getchar();}
	while(isdigit(c)){t=t*10+c-'0';c=getchar();}
	if(f)t=-t;
}

const int inf=0x3f3f3f3f;
const int maxn=1005,maxm=6005;
int n,m;
int S,T,c1,c2;
int ans;
 
struct edge
{
	int u,v,f,nxt;
}g[maxm*2];

int head[maxn],ecnt=1;
void eADD(int u,int v,int f)
{
//	cerr<<u<<" "<<v<<" "<<f<<endl;
	g[++ecnt].u=u;g[ecnt].v=v;g[ecnt].f=f;g[ecnt].nxt=head[u];head[u]=ecnt;
	g[++ecnt].u=v;g[ecnt].v=u;g[ecnt].f=0;g[ecnt].nxt=head[v];head[v]=ecnt;
}

int dep[maxn];
bool BFS()
{
	queue<int> q;
	memset(dep,0,sizeof(dep));
	dep[S]=1;
	q.push(S);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();	
		for(register int i=head[u];i;i=g[i].nxt)
		{
			int v=g[i].v;
			if(!dep[v] && g[i].f)
			{
				dep[v]=dep[u]+1;
				if(v==T)return true;
				q.push(v);
			}
		}
	}
	return false;
}

int dfs(int u,int infl)
{
	if(u==T)return infl;
	int rest=infl;
	for(register int i=head[u];i && rest;i=g[i].nxt)
	{
		int v=g[i].v;
		if(dep[v]==dep[u]+1 && g[i].f)
		{
			int flow=dfs(v,min(g[i].f,rest));
			rest-=flow;
			g[i].f-=flow;
			g[i^1].f+=flow;
		}
	}
	return infl-rest;
}

int main()
{
	read(n),read(m),read(c1),read(c2);
	for(register int i=1;i<=n;++i)
		eADD(i(i),o(i),1);
	for(register int i=1;i<=m;++i)
	{
		int u,v;
		read(u),read(v);
		eADD(o(u),i(v),inf);
		eADD(o(v),i(u),inf);
	}
	S=o(c1),T=i(c2);
	while(BFS())
		ans+=dfs(S,inf);
	printf("%d",ans);
	return 0;
}