【最小割】线性代数

数论, 网络流

传送鸡：BZOJ3996

TJOI2015

套路题

先转化题意（好复杂）

题目实际上是要求把一堆点分两堆，一堆选择，另一堆不选，选择点i需要$c_i$代价，同时选择(i,j)可以得到收益$b_{i,j}$。

由于最小割只能求最小代价，先要转化。

不妨假设收益最大化为sum，然后建立源点s和汇点t，和s连接表示选择，和t连接表示不选。

由于是s-t割，一个点必然是选或者不选。

然后把源点s和点(i,j)连容量为$b_{i,j}$的边，因为已经假设收益最大化，最后如果最后切断则表示不选(i,j)的代价；

同样把点i和汇点t连容量$c_i$的边，最后如果切断则表示选择i的代价。

完成建图后，跑最小割

PS：这道题的一般形式就是最大闭合权子图（by梁大）

贴代码：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define INF 100000000
int sum,n,x,s,t,tot,head[800030],iter[800030],level[800030],q[800030];
struct edge{int v,cap,rev,nxt;}E[3000030];
void add(int x,int y,int k){
	E[++tot].v=y; E[tot].cap=k; E[tot].rev=tot+1; E[tot].nxt=head[x]; head[x]=tot;
	E[++tot].v=x; E[tot].cap=0; E[tot].rev=tot-1; E[tot].nxt=head[y]; head[y]=tot;
}
void bfs(int s){
	memset(level,-1,sizeof level);
	int t=0,w=1;
	level[s]=0; q[1]=s;
	while (t<w){
		t++;
		int v=q[t];
		for (int i=head[v];i;i=E[i].nxt){
			edge &e=E[i];
			if (e.cap>0 && level[e.v]<0){
				level[e.v]=level[v]+1;
				q[++w]=e.v;
			}
		}
	}
}
int dfs(int v,int t,int f){
	if (v==t) return f;
	for (int &i=iter[v];i;i=E[i].nxt){
		edge &e=E[i];
		if (e.cap>0 && level[v]<level[e.v]){
			int d=dfs(e.v,t,min(f,e.cap));
			if (d>0){
				e.cap-=d;
				E[e.rev].cap+=d;
				return d;
			}
		}
	}
	return 0;
}
int dinic(int s,int t){
	int flow=0;
	for(;;){
		bfs(s);
		if (level[t]<0) return flow;
		for (int i=1;i<=2*n*n+1;i++) iter[i]=head[i];
		int f=0;
		while ((f=dfs(s,t,INF))>0)
			flow+=f;
	}
}
int main(){
	scanf("%d",&n);
	s=2*n*n; t=2*n*n+1;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++){
			scanf("%d",&x);
			sum+=x;
			add(s,i*n+j+n,x);
			add(i*n+j+n,i,INF);
			add(i*n+j+n,j,INF);
		}
	for (int i=1;i<=n;i++){
		scanf("%d",&x);
		add(i,t,x);
	}
	
	printf("%d\n",sum-dinic(s,t));
	
	return 0;
}