最小割边数量的最小求法。
简要题意
给定一张有 $n$ 个结点和 $m$ 条边的网络，源点为 $1$ ，汇点为 $n$ ，求最小割，以及满足最小割的最小割边数。
注意：这里的 $n$ 并不是输入的 $n$ 。
题解
总而言之，这就是道最小割的模板题，直接跑一遍最小割就可以了。
那么，我们应该如何考虑求取最小割边数呢。
我们应该明晰的是：最小割所割的边一定是网络中的关键边，即在最大流流完之后没有流量的边，但是关键边不一定是最小割边。这是显然的。
回忆最小割的定义：花费最小代价把网络分割成两个集合，分别包含 $S,T$ ，那么，最小割边的两个端点也就自然应该在两个集合中。
所以，可以考虑从源点开始搜索一次，经过残余网络能够到达的结点就属于 $S$ ，从汇点开始搜索一次，经过残余网络能够到达的结点就属于 $T$ ，然后枚举边，看两个端点是否分别属于两个集合即可。
理论正确，但是实测 $60pt$ 。
那我们换一种思路，我曾在学习笔记中写到过：当所有边的容量都变成 $1$ 的时候，最小割就等于最小割边数，我们可以利用这一结论。
但是如果我们建立两个网络，一个跑第一问，一个跑第二问，是否有些不划算？
显然。
所以，我们考虑能够一次性解决两个问题的网络：构造一个大质数（不是质数也行），然后把每一条边的边权转换为 $w\times P+1$ ，为什么？
然后我们发现：$\displaystyle\left\lfloor\frac{wP+1}{P}\right\rfloor=w,(wP+1)\bmod P=1$ ，那显然：
$\displaystyle\sum_{m}\left\lfloor\frac{wP+1}{P}\right\rfloor=\sum_{m}w=maxflow$
只要满足 $\displaystyle P>\sum_{m}$ 就好了，即 $P>1000$ 。
最小割的答案就是 $\frac{res}{P}$ ，而最小割边数的答案就是 $res\bmod P$ 。
AC 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
| const int MAXN=1e2+10,MAXM=2e3+10;
const ll INF=0x1145141919810;
const ll NUM=2e6;
int N,M,S,T;
struct Net
{
int next,to;
ll val;
}Edge[MAXM<<1];
int Head[MAXN],Cur[MAXN],Total=1;
inline void addEdge(int u,int v,ll w)
{
Edge[++Total]=(Net){Head[u],v,w};Head[u]=Total;
Edge[++Total]=(Net){Head[v],u,0};Head[v]=Total;
}
int Fl[MAXN];
inline bool Bfs()
{
for(int i=S;i<=T;++i) Fl[i]=-1;
std::queue<int>Q;
Q.push(S),Cur[S]=Head[S],Fl[S]=0;
while(!Q.empty())
{
int x=Q.front();Q.pop();
for(int e=Head[x],v;e;e=Edge[e].next)
{
v=Edge[e].to;
if(Fl[v]==-1&&Edge[e].val)
{
Fl[v]=Fl[x]+1,Cur[v]=Head[v];
if(v==T) return 1;
Q.push(v);
}
}
}
return 0;
}
ll Dfs(int x,ll inf)
{
if(x==T) return inf;
ll flow=0;
for(int e=Cur[x],v;e&&flow<inf;e=Edge[e].next)
{
v=Edge[e].to,Cur[x]=e;
if(Fl[v]==Fl[x]+1&&Edge[e].val)
{
ll k=Dfs(v,std::min(Edge[e].val,inf-flow));
if(!k) Fl[v]=-1;
Edge[e].val-=k,Edge[e^1].val+=k,flow+=k;
}
}
return flow;
}
inline ll Dinic()
{
ll r=0,flow;
while(Bfs()) while(flow=Dfs(S,INF)) r+=flow;
return r;
}
int main()
{
read(N,M);
S=1,T=N;
for(int i=1,u,v;i<=M;++i)
{
ll w;
read(u,v,w);
addEdge(u,v,1ll*w*(NUM+1)+1);
checkMax(T,u),checkMax(T,v);
}
ll maxFlow=Dinic();
write(maxFlow/(NUM+1),' ',maxFlow%(NUM+1));
return 0;
}
|
后话
这个方法有些投机取巧，且容易爆 long long。
在 $\text{USACO}$ 的原题中，还有第三问：求最小割边集，意思是，求一种字典序最小的割边方案。这样的话，第二种方法似乎就行不通了（说不定还可以），但是如果是第一种方法的话，是能够通过枚举得到的，且能够和求取最小割边数的时候一起得到。
不过呢，将计就计便是一种策略。
在条件允许（数据小）的情况下， 有一种求字典序最小的割边集做法：枚举每一条边并删除，如果删除了这条边导致最小割变大，说明这条边是关键割边，记录答案即可，但这样时间复杂度略高，不过解决这道题足够了。