网络流拓展二

自用笔记算法

网络流拓展二

POJ 3680(区间k覆盖问题+离散)

题目要求

枢轴上有一些带权值的区间 选出权和尽量大的一些区间 使得任意一个数最多被k个区间覆盖

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 410
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
struct Edge{
	int from,to,cap,flow,cost;
	Edge(int from,int to,int cap,int flow,int cost):from(from),to(to),cap(cap),flow(flow),cost(cost){}
};
struct MCMF{
	int n,m,s,t;
	vector<Edge>edges;
	vector<int>G[maxn];
	int inq[maxn],d[maxn],p[maxn],a[maxn];
	void init(int n){
		this->n=n;
		for(int i=0;i<n;i++) G[i].clear();
		edges.clear();
	}
	void AddEdge(int from,int to,int cap,int cost){
		edges.push_back(Edge(from,to,cap,0,cost));
		edges.push_back(Edge(to,from,0,0,-cost));
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	bool BellmanFord(int s,int t,int &flow,int& cost){
		for(int i=0;i<n;i++) d[i]=inf;
		memset(inq,0,sizeof(inq));
		d[s]=0,inq[s]=1,p[s]=0,a[s]=inf;
		queue<int>Q;
		Q.push(s);
		while(!Q.empty()){
			int u=Q.front();  Q.pop();
			inq[u]=0;
			for(int i=0;i<G[u].size();i++){
				Edge& e=edges[G[u][i]];
				if(e.cap>e.flow && d[e.to]>d[u]+e.cost){
					d[e.to]=d[u]+e.cost;
					p[e.to]=G[u][i];
					a[e.to]=min(a[u],e.cap-e.flow);
					if(!inq[e.to]){
						Q.push(e.to);
						inq[e.to]=1;
					}
				}
			}
		}
		if(d[t]==inf) return false;
		flow+=a[t];
		cost+=d[t]*a[t];
		int u=t;
		while(u!=s){
			edges[p[u]].flow+=a[t];
			edges[p[u]^1].flow-=a[t];
			u=edges[p[u]].from;
		}
		return true;
	}
	int Mincost(int s,int t){
		int flow=0,cost=0;
		while(BellmanFord(s,t,flow,cost));
		return cost;
	}
}mc;
int l[maxn],r[maxn],w[maxn],temp[maxn];
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		int nn,k;
		cin>>nn>>k;
		int cnt=0,mm=1;
		mc.init(maxn);
		for(int i=1;i<=nn;i++){
			cin>>l[i]>>r[i]>>w[i];
			temp[++cnt]=l[i];
			temp[++cnt]=r[i];
		}
		sort(temp+1,temp+1+cnt);
		for(int i=2;i<=cnt;i++){
			if(temp[i]!=temp[i-1]) temp[++mm]=temp[i];
		}
		int S=0,T=mm+1;
		for(int i=2;i<=mm;i++) mc.AddEdge(i-1,i,k,0);
		for(int i=1;i<=nn;i++){
			int u=lower_bound(temp+1,temp+1+mm,l[i])-temp;
			int v=lower_bound(temp+1,temp+1+mm,r[i])-temp;
			mc.AddEdge(u,v,1,-w[i]);
		}
		mc.AddEdge(S,1,k,0);
		mc.AddEdge(mm,T,k,0);
		int ans=-mc.Mincost(S,T);
		cout<<ans<<endl;
	}
	return 0;
}

思路

MCMF解法：
把所有点排序后离散化去重
相邻点加边 容量为k 费用为0
对于原来的区间[l,r] 找到排序后l和r的位置建边 容量为1 费用为-w
源点到点1建边 容量为k 费用为0 满足最多k区间覆盖
点mm到汇点建边 容量为k 费用为0
跑一遍MCMF 答案取反就是所求(求的是最大 MCMF是最小费用)

HDU 4106(区间k覆盖变形)

题目要求

一共有n个水果 每个水果有一个权值 在连续m个水果中最多只能划k个 问所能划到的最大权值

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 1050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
struct Edge{
	int from,to,cap,flow,cost;
	Edge(int from,int to,int cap,int flow,int cost):from(from),to(to),cap(cap),flow(flow),cost(cost){}
};
struct MCMF{
	int n,m,s,t;
	vector<Edge>edges;
	vector<int>G[maxn];
	int inq[maxn],d[maxn],p[maxn],a[maxn];
	void init(int n){
		this->n=n;
		for(int i=0;i<n;i++) G[i].clear();
		edges.clear();
	}
	void AddEdge(int from,int to,int cap,int cost){
		edges.push_back(Edge(from,to,cap,0,cost));
		edges.push_back(Edge(to,from,0,0,-cost));
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	bool BellmanFord(int s,int t,int &flow,int& cost){
		for(int i=0;i<n;i++) d[i]=inf;
		memset(inq,0,sizeof(inq));
		d[s]=0,inq[s]=1,p[s]=0,a[s]=inf;
		queue<int>Q;
		Q.push(s);
		while(!Q.empty()){
			int u=Q.front();  Q.pop();
			inq[u]=0;
			for(int i=0;i<G[u].size();i++){
				Edge& e=edges[G[u][i]];
				if(e.cap>e.flow && d[e.to]>d[u]+e.cost){
					d[e.to]=d[u]+e.cost;
					p[e.to]=G[u][i];
					a[e.to]=min(a[u],e.cap-e.flow);
					if(!inq[e.to]){
						Q.push(e.to);
						inq[e.to]=1;
					}
				}
			}
		}
		if(d[t]==inf) return false;
		flow+=a[t];
		cost+=d[t]*a[t];
		int u=t;
		while(u!=s){
			edges[p[u]].flow+=a[t];
			edges[p[u]^1].flow-=a[t];
			u=edges[p[u]].from;
		}
		return true;
	}
	int Mincost(int s,int t){
		int flow=0,cost=0;
		while(BellmanFord(s,t,flow,cost));
		return cost;
	}
}mc;
int w[maxn];
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int nn,mm,k;
	while(cin>>nn>>mm>>k){
		int sum=0;
		int S=0,T=nn-mm+3;
		int fin=T-1;
		for(int i=1;i<=nn;i++){
			cin>>w[i];
			sum+=w[i];
		}
		if(k==mm){
			cout<<sum<<endl;
			continue;
		}
		mc.init(maxn);
		for(int i=1;i<fin;i++) mc.AddEdge(i,i+1,k,0);
		mc.AddEdge(S,1,k,0);
		mc.AddEdge(fin,T,k,0);
		for(int i=1;i<=nn;i++){
			int l=max(1,i-mm+1);
			int r=min(i,fin-1)+1;
			mc.AddEdge(l,r,1,-w[i]);
		}
		int ans=-mc.Mincost(S,T);
		cout<<ans<<endl;
	}
	return 0;
}

思路

POJ3680是区间内对点的限制 而本题是点对区间的限制 所以把区间变点 点代表区间
在n个点里面一共有n-m+1个长度为m的区间，现在把这n-m+1个区间两两之间用点隔开，那么一共用n-m+2个点
如果选n这个点则从点max(1,i-m+1)到点min(fin-1,i)+1之间的区间每个点(此点代表的是线段)可选的点数就会减一
除此之外其余的建边与上题一样 加剪枝防tle

POJ 3762(同3680)

题目要求

给出n个任务 每个任务给出一天内的时间间隔以及完成的分数
给出k天时间 问能获得的最大分数

参考AC代码

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<bits/stdc++.h>
#define maxn 4050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
struct Edge{
	int from,to,cap,flow,cost;
	Edge(int from,int to,int cap,int flow,int cost):from(from),to(to),cap(cap),flow(flow),cost(cost){}
};
struct MCMF{
	int n,m,s,t;
	vector<Edge>edges;
	vector<int>G[maxn];
	int inq[maxn],d[maxn],p[maxn],a[maxn];
	void init(int n){
		this->n=n;
		for(int i=0;i<n;i++) G[i].clear();
		edges.clear();
	}
	void AddEdge(int from,int to,int cap,int cost){
		edges.push_back(Edge(from,to,cap,0,cost));
		edges.push_back(Edge(to,from,0,0,-cost));
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	bool BellmanFord(int s,int t,int &flow,int& cost){
		for(int i=0;i<n;i++) d[i]=inf;
		memset(inq,0,sizeof(inq));
		d[s]=0,inq[s]=1,p[s]=0,a[s]=inf;
		queue<int>Q;
		Q.push(s);
		while(!Q.empty()){
			int u=Q.front();  Q.pop();
			inq[u]=0;
			for(int i=0;i<G[u].size();i++){
				Edge& e=edges[G[u][i]];
				if(e.cap>e.flow && d[e.to]>d[u]+e.cost){
					d[e.to]=d[u]+e.cost;
					p[e.to]=G[u][i];
					a[e.to]=min(a[u],e.cap-e.flow);
					if(!inq[e.to]){
						Q.push(e.to);
						inq[e.to]=1;
					}
				}
			}
		}
		if(d[t]==inf) return false;
		flow+=a[t];
		cost+=d[t]*a[t];
		int u=t;
		while(u!=s){
			edges[p[u]].flow+=a[t];
			edges[p[u]^1].flow-=a[t];
			u=edges[p[u]].from;
		}
		return true;
	}
	int Mincost(int s,int t){
		int flow=0,cost=0;
		while(BellmanFord(s,t,flow,cost));
		return cost;
	}
}mc;
int l[maxn],r[maxn],w[maxn],temp[maxn];
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	int nn,k;
	while(scanf("%d%d",&nn,&k)!=EOF){
		int len=0,len2=1;
		mc.init(maxn);
		for(int i=1;i<=nn;i++){
			int h1,m1,s1,h2,m2,s2;
			scanf("%d:%d:%d %d:%d:%d %d",&h1,&m1,&s1,&h2,&m2,&s2,&w[i]);
			int temp1=h1*3600+m1*60+s1;
			int temp2=h2*3600+m2*60+s2;
			l[i]=temp1,r[i]=temp2;
			temp[++len]=temp1,temp[++len]=temp2;
		}
		sort(temp+1,temp+1+len);
		for(int i=2;i<=len;i++){
			if(temp[i]!=temp[i-1]) temp[++len2]=temp[i];
		}
		int S=0,T=len2+1;
		mc.AddEdge(S,1,k,0);
		mc.AddEdge(T-1,T,k,0);
		for(int i=1;i<len2;i++) mc.AddEdge(i,i+1,k,0);
		for(int i=1;i<=nn;i++){
			int u=lower_bound(temp+1,temp+1+len2,l[i])-temp;
			int v=lower_bound(temp+1,temp+1+len2,r[i])-temp;
			mc.AddEdge(u,v,1,-w[i]);
		}
		int ans=-mc.Mincost(S,T);
		printf("%d\n",ans);
	}
	return 0;
}

思路

同3680
每个时刻最多重叠k次(k天)
注意本题输入最好用scanf 用scanf不能取消流的限制

POJ 3422(区间累计k覆盖最大值)

题目要求

N*N的地图上每格都有分数，分数只能获取一次。有人从左上方开始，每次向右或下移动一格，到右下方为止，记为一次环游。问第K次环游后累计分数的最大值

参考AC代码

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
#include <iostream>
#include <vector>
#include <queue>
#include<cstring>
#define maxn 5050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
struct Edge{
	int from,to,cap,flow,cost;
	Edge(int from,int to,int cap,int flow,int cost):from(from),to(to),cap(cap),flow(flow),cost(cost){}
};
struct MCMF{
	int n,m,s,t;
	vector<Edge>edges;
	vector<int>G[maxn];
	int inq[maxn],d[maxn],p[maxn],a[maxn];
	void init(int n){
		this->n=n;
		for(int i=0;i<n;i++) G[i].clear();
		edges.clear();
	}
	void AddEdge(int from,int to,int cap,int cost){
		edges.push_back(Edge(from,to,cap,0,cost));
		edges.push_back(Edge(to,from,0,0,-cost));
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	bool BellmanFord(int s,int t,int &flow,int& cost){
		for(int i=0;i<n;i++) d[i]=inf;
		memset(inq,0,sizeof(inq));
		d[s]=0,inq[s]=1,p[s]=0,a[s]=inf;
		queue<int>Q;
		Q.push(s);
		while(!Q.empty()){
			int u=Q.front();  Q.pop();
			inq[u]=0;
			for(int i=0;i<G[u].size();i++){
				Edge& e=edges[G[u][i]];
				if(e.cap>e.flow && d[e.to]>d[u]+e.cost){
					d[e.to]=d[u]+e.cost;
					p[e.to]=G[u][i];
					a[e.to]=min(a[u],e.cap-e.flow);
					if(!inq[e.to]){
						Q.push(e.to);
						inq[e.to]=1;
					}
				}
			}
		}
		if(d[t]==inf) return false;
		flow+=a[t];
		cost+=d[t]*a[t];
		int u=t;
		while(u!=s){
			edges[p[u]].flow+=a[t];
			edges[p[u]^1].flow-=a[t];
			u=edges[p[u]].from;
		}
		return true;
	}
	int Mincost(int s,int t){
		int flow=0,cost=0;
		while(BellmanFord(s,t,flow,cost));
		return cost;
	}
}mc;
int a[55][55],mark[55][55];
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int nn,k;
	while(cin>>nn>>k){
		mc.init(maxn);
		mm(mark,0);
		int num=0;
		for(int i=1;i<=nn;i++){
			for(int j=1;j<=nn;j++){
				cin>>a[i][j];
				mark[i][j]=++num;
			}
		}
		int S=0,T=2*num+1;
		mc.AddEdge(S,1,k,0);
		mc.AddEdge(T-1,T,k,0);
		for(int i=1;i<=nn;i++){
			for(int j=1;j<=nn;j++){
				int u=mark[i][j],v=u+num;
				mc.AddEdge(u,v,1,-a[i][j]);
				mc.AddEdge(u,v,k,0);
				if(i<nn) mc.AddEdge(v,u+nn,k,0);
				if(j<nn) mc.AddEdge(v,u+1,k,0);
 			}
		}
		int ans=-mc.Mincost(S,T);
		cout<<ans<<endl;
	}
	return 0;
}

思路

可以为每个点创建伪点，由两条有向边相连。原始点到伪点连一条容量为1，权值为负分数的边；原始点到伪点连一条容量为k，权值为0的边。
前者表示分数只能拿一次，后者表示第二次第三次……可以继续走这个点，但是不拿分数。
多源多汇问题 建一个超级源点连向(1,1)位置 建一个超级汇点与(n,n)相连 流量为k 费用为0
u连向v代表拆点的部分 v连向u代表向下和向右的过程

HDU 3667(费用与流量平方)

题目要求

容量c均为整数 并且每条弧还有一个费用系数a 表示该弧流量为x时费用为ax²
问流量是否可以满足k 若满足输出最小费用那个 不满足输出-1

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 105
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int k;
struct Edge{
	int from,to,cap,flow,cost;
	Edge(int from,int to,int cap,int flow,int cost):from(from),to(to),cap(cap),flow(flow),cost(cost){}
};
struct MCMF{
	int n,m,s,t;
	vector<Edge>edges;
	vector<int>G[maxn];
	int inq[maxn],d[maxn],p[maxn],a[maxn];
	void init(int n){
		this->n=n;
		for(int i=0;i<n;i++) G[i].clear();
		edges.clear();
	}
	void AddEdge(int from,int to,int cap,int cost){
		edges.push_back(Edge(from,to,cap,0,cost));
		edges.push_back(Edge(to,from,0,0,-cost));
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	bool BellmanFord(int s,int t,int &flow,int& cost){
		for(int i=0;i<n;i++) d[i]=inf;
		memset(inq,0,sizeof(inq));
		d[s]=0,inq[s]=1,p[s]=0,a[s]=inf;
		queue<int>Q;
		Q.push(s);
		while(!Q.empty()){
			int u=Q.front();  Q.pop();
			inq[u]=0;
			for(int i=0;i<G[u].size();i++){
				Edge& e=edges[G[u][i]];
				if(e.cap>e.flow && d[e.to]>d[u]+e.cost){
					d[e.to]=d[u]+e.cost;
					p[e.to]=G[u][i];
					a[e.to]=min(a[u],e.cap-e.flow);
					if(!inq[e.to]){
						Q.push(e.to);
						inq[e.to]=1;
					}
				}
			}
		}
		if(d[t]==inf) return false;
		flow+=a[t];
		cost+=d[t]*a[t];
		int u=t;
		while(u!=s){
			edges[p[u]].flow+=a[t];
			edges[p[u]^1].flow-=a[t];
			u=edges[p[u]].from;
		}
		return true;
	}
	void Mincost(int s,int t){
		int flow=0,cost=0;
		while(BellmanFord(s,t,flow,cost));
		if(flow<k) cout<<"-1"<<endl;
		else cout<<cost<<endl;
	}
}mc;
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int nn,mm;
	while(cin>>nn>>mm>>k){
		 mc.init(maxn);
		 int S=0,T=nn;
		 mc.AddEdge(S,1,k,0);
		 for(int i=1;i<=mm;i++){
		 	int u,v,a,c;
		 	cin>>u>>v>>a>>c;
		 	for(int k=1;k<=c;k++){
		 		int x=2*k-1;
		 		mc.AddEdge(u,v,1,x*a);
			 } 
		 }
		 mc.Mincost(S,T);
	}
	return 0;
}

思路

蓝书P366
拆边 容量为c 就把u-v拆成c条边 每条变容量为1 费用为a 3a 5a···
跑MCMF即可
本题需要注意多了一个是否满足k流 所以需要判断flow==k时输出mincost 否则不满足k流直接输出-1
S=0 与点1额外建边容量为k 费用为0 把流量限制在k之内 防止重边的干扰

UVA 11613(流量不固定s-t最小费用流)

题目要求

给出m个月 每个月可以生产make_limit个产品 成本为make_cost 该月售价为price 最多售出sell_price件
每个产品可以封存max_store月 每个产品每个月封存需要花store_cost的钱
问这m个月能获得的最大利润是多少

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 210
#define inf 1000000000
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const int INF=1000000000;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
struct Edge{
	int from,to,cap,flow,cost;
	Edge(int from,int to,int cap,int flow,int cost):from(from),to(to),cap(cap),flow(flow),cost(cost){}
};
struct MCMF{
	int n,m,s,t;
	vector<Edge>edges;
	vector<int>G[maxn];
	int inq[maxn],d[maxn],p[maxn],a[maxn];
	void init(int n){
		this->n=n;
		for(int i=0;i<n;i++) G[i].clear();
		edges.clear();
	}
	void AddEdge(int from,int to,int cap,int cost){
		edges.push_back(Edge(from,to,cap,0,cost));
		edges.push_back(Edge(to,from,0,0,-cost));
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	bool BellmanFord(int s,int t,LL& ans){
		for(int i=0;i<n;i++) d[i]=inf;
		memset(inq,0,sizeof(inq));
		d[s]=0,inq[s]=1,p[s]=0,a[s]=inf;
		queue<int>Q;
		Q.push(s);
		while(!Q.empty()){
			int u=Q.front();  Q.pop();
			inq[u]=0;
			for(int i=0;i<G[u].size();i++){
				Edge& e=edges[G[u][i]];
				if(e.cap>e.flow && d[e.to]>d[u]+e.cost){
					d[e.to]=d[u]+e.cost;
					p[e.to]=G[u][i];
					a[e.to]=min(a[u],e.cap-e.flow);
					if(!inq[e.to]){
						Q.push(e.to);
						inq[e.to]=1;
					}
				}
			}
		}
		if(d[t]>0) return false;
		ans+=(LL)d[t]*(LL)a[t];
		int u=t;
		while(u!=s){
			edges[p[u]].flow+=a[t];
			edges[p[u]^1].flow-=a[t];
			u=edges[p[u]].from;
		}
		return true;
	}
	LL Mincost(int s,int t){
		LL cost=0;
		while(BellmanFord(s,t,cost));
		return cost;
	}
}mc;
int flag=1;
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		mc.init(maxn);
		int month,store_cost;
		cin>>month>>store_cost;
		int S=0,T=2*month+1;
		for(int i=1;i<=month;i++){
			int make_cost,make_limit,price,sell_limit,max_store;
			cin>>make_cost>>make_limit>>price>>sell_limit>>max_store;
			mc.AddEdge(S,i,make_limit,make_cost);
			mc.AddEdge(i+month,T,sell_limit,-price);
			for(int j=0;j<=max_store;j++){
				if(i+j<=month) mc.AddEdge(i,month+i+j,inf,store_cost*j);
			}
		}
		LL ans=-mc.Mincost(S,T);
		cout<<"Case "<<flag++<<": "<<ans<<endl;
	}
	return 0;
}

思路

蓝书P367
费用有正有负
在最短增广路费用为正时停止增光
流量不固定 BF里不需要flow参数 开LL
建超级源点和超级汇点 建图 月份和月份之间保存封存的费用

LA 3231(公平分配问题)

题目要求

把m个任务分配给n个处理器 其中每个任务有两个候选处理器 可任选一个分配 要求所有处理器中 任务数最多的那个处理器所分配的任务数
尽量少 不同任务的候选处理器集保证不同

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 11005
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
struct Edge{
  int from, to, cap, flow;
};
struct Dinic{
  int n, m, s, t;
  vector<Edge> edges;   
  vector<int> G[maxn];   
  bool vis[maxn];         
  int d[maxn];           
  int cur[maxn];       
void ClearAll(int n){
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
}
void AddEdge(int from, int to, int cap){
    edges.push_back((Edge){from, to, cap, 0});
    edges.push_back((Edge){to, from, 0, 0});
    m = edges.size();
    G[from].push_back(m-2);
    G[to].push_back(m-1);
}
bool BFS(){
    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    Q.push(s);
    vis[s] = 1;
    d[s] = 0;
    while(!Q.empty()) {
      int x = Q.front(); Q.pop();
      for(int i = 0; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i]];
        if(!vis[e.to] && e.cap > e.flow) {
          vis[e.to] = 1;
          d[e.to] = d[x] + 1;
          Q.push(e.to);
        }
      }
    }
    return vis[t];
}
int DFS(int x, int a){
    if(x == t || a == 0) return a;
    int flow = 0, f;
    for(int& i = cur[x]; i < G[x].size(); i++) {
      Edge& e = edges[G[x][i]];
      if(d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > 0) {
        e.flow += f;
        edges[G[x][i]^1].flow -= f;
        flow += f;
        a -= f;
        if(a == 0) break;
      }
    }
    return flow;
}
int Maxflow(int s, int t){
    this->s = s; this->t = t;
    int flow = 0;
    while(BFS()) {
      memset(cur, 0, sizeof(cur));
      flow += DFS(s, inf);
    }
    return flow;
  }
}g;
vector<pii>e;
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		int nn,mm;
		cin>>nn>>mm;
		int l=1,r=mm,ans=0;
		for(int i=1;i<=mm;i++){
			int x,y;
			cin>>x>>y;
			e.pb(mp(x,y));
		}
		while(l<=r){
			int S=0,T=nn+mm+1;
			int mid=(l+r)>>1;
			g.ClearAll(maxn);
			for(int i=1;i<=mm;i++){
				g.AddEdge(S,i,1);
				g.AddEdge(i,e[i-1].fi+mm,1);
				g.AddEdge(i,e[i-1].se+mm,1);
			}
			for(int i=1;i<=nn;i++) g.AddEdge(i+mm,T,mid);
			if(g.Maxflow(S,T)==mm){
				ans=mid;
				r=mid-1;
			}
			else l=mid+1;
		}
		cout<<ans<<endl;
	}
	return 0;
}

思路

二分网络流
蓝书P367

ZOJ 2587(最小割唯一判断)

题目要求

给出一张无向网络图,并给出起点和终点,破坏图的每一条边需要一定的费用,问破坏起点和终点的连通性的费用是否唯一.

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 850
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
struct Edge {
	int from, to, cap, flow;
};
struct Dinic {
	int n, m, s, t;
	vector<Edge> edges;
	vector<int> G[maxn];
	bool vis[maxn];
	int d[maxn];
	int cur[maxn];
	int vis1[maxn],vis2[maxn];
	int cnt1,cnt2;
	void ClearAll(int n) {
		for(int i = 0; i < n; i++) G[i].clear();
		edges.clear();
	}
	void AddEdge(int from, int to, int cap) {
		edges.push_back((Edge){from, to, cap, 0});
		edges.push_back((Edge){to, from, cap, 0});
		m = edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	bool BFS() {
		memset(vis, 0, sizeof(vis));
		queue<int> Q;
		Q.push(s);
		vis[s] = 1;
		d[s] = 0;
		while(!Q.empty()) {
			int x = Q.front();
			Q.pop();
			for(int i = 0; i < G[x].size(); i++) {
				Edge& e = edges[G[x][i]];
				if(!vis[e.to] && e.cap > e.flow) {
					vis[e.to] = 1;
					d[e.to] = d[x] + 1;
					Q.push(e.to);
				}
			}
		}
		return vis[t];
	}
	int DFS(int x, int a) {
		if(x == t || a == 0) return a;
		int flow = 0, f;
		for(int& i = cur[x]; i < G[x].size(); i++) {
			Edge& e = edges[G[x][i]];
			if(d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > 0) {
				e.flow += f;
				edges[G[x][i]^1].flow -= f;
				flow += f;
				a -= f;
				if(a == 0) break;
			}
		}
		return flow;
	}
	int Maxflow(int s, int t) {
		this->s = s;
		this->t = t;
		int flow = 0;
		while(BFS()) {
			memset(cur, 0, sizeof(cur));
			flow += DFS(s, inf);
		}
		return flow;
	}
	void dfs1(int x) {
		vis1[x]=1;
		cnt1++;
		for(int i=0;i<G[x].size();i++){
			int k=G[x][i];
			if(!vis1[edges[k].to] && edges[k].cap>edges[k].flow){
				dfs1(edges[k].to);
			}
		}
	}
	void dfs2(int x) {
		vis2[x]=1;
		cnt2++;
		for(int i=0;i<G[x].size();i++){
			int k=G[x][i];
			if(!vis2[edges[k].to] && edges[k^1].cap>edges[k^1].flow){
				dfs2(edges[k].to);
			}
		}
	}
}g;
int nn,mm,S,T;
int main() {
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	while(cin>>nn>>mm>>S>>T) {
		if(nn==0 && mm==0 && S==0 && T==0) break;
		g.ClearAll(maxn);
		for(int i=1; i<=mm; i++) {
			int x,y,c;
			cin>>x>>y>>c;
			g.AddEdge(x,y,c);
		}
		int ans=g.Maxflow(S,T);
		mm(g.vis1,0),mm(g.vis2,0);
		g.cnt1=0,g.cnt2=0;
		g.dfs1(S),g.dfs2(T);
		if(g.cnt1+g.cnt2==nn) cout<<"UNIQUE"<<endl;
		else cout<<"AMBIGUOUS"<<endl;
	}
	return 0;
}

思路

破坏两点的连通性的最小费用,很容易联想到 网络流中的最小割,
建立源点 汇点 同时 因为图是无向图,我们需要将每条边建两次(正反向) 也可以直接把反向容量设为cap
然后就是判断这个最小割是否唯一了：
首先 从源点开始 dfs 通过非饱和边 统计所有能走到的点 记为s1
然后 从汇点开始 dfs 通过非饱和边 统计所有能走到的点 记为s2
如果s1+s2==n则说明最小割唯一

UVA 11248(扩弧)

题目要求

给定一个有向网络 每条变均有一个容量 问是否存在一个从点1到点N 流量为C的流 如果不存在 是否可以恰好修改一条弧的容量 使得存在这样的流
蓝书P368

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 105
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
struct Edge{
  int from, to, cap, flow;
};
int cmp(Edge a,Edge b){
	if(a.from==b.from) return a.to<b.to;
	return a.from<b.from;
}
struct Dinic{
  int n, m, s, t;
  vector<Edge> edges;   
  vector<int> G[maxn];   
  bool vis[maxn];         
  int d[maxn];           
  int cur[maxn];       
void ClearAll(int n){
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
}
void ClearFlow(){
    for(int i=0;i<edges.size();i++) edges[i].flow=0;    
}
void AddEdge(int from, int to, int cap){
    edges.push_back((Edge){from, to, cap, 0});
    edges.push_back((Edge){to, from, 0, 0});
    m = edges.size();
    G[from].push_back(m-2);
    G[to].push_back(m-1);
}
bool BFS(){
    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    Q.push(s);
    vis[s] = 1;
    d[s] = 0;
    while(!Q.empty()) {
      int x = Q.front(); Q.pop();
      for(int i = 0; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i]];
        if(!vis[e.to] && e.cap > e.flow) {
          vis[e.to] = 1;
          d[e.to] = d[x] + 1;
          Q.push(e.to);
        }
      }
    }
    return vis[t];
}
int DFS(int x, int a){
    if(x == t || a == 0) return a;
    int flow = 0, f;
    for(int& i = cur[x]; i < G[x].size(); i++) {
      Edge& e = edges[G[x][i]];
      if(d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > 0) {
        e.flow += f;
        edges[G[x][i]^1].flow -= f;
        flow += f;
        a -= f;
        if(a == 0) break;
      }
    }
    return flow;
}
int Maxflow(int s, int t){
    this->s = s; this->t = t;
    int flow = 0;
    while(BFS()) {
      memset(cur, 0, sizeof(cur));
      flow += DFS(s, inf);
    }
    return flow;
}
vector<int>Mincut(){    
	vector<int> ans;
	for(int i=0;i<edges.size();i++){
  		Edge& e=edges[i];
  		if(vis[e.from] && !vis[e.to] && e.cap>0) ans.push_back(i);
	}
	return ans;
}
void Reduce(){   
    for(int i=0;i<edges.size();i++) edges[i].cap-=edges[i].flow;
  }
}g;
int nn,mm,c;
int flag=1;
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	while(cin>>nn>>mm>>c){
		if(nn==0 && mm==0 && c==0) break;
		cout<<"Case "<<flag++<<": ";
		g.ClearAll(maxn);
		for(int i=1;i<=mm;i++){
			int x,y,z;
			cin>>x>>y>>z;
			g.AddEdge(x,y,z);
		}
		int S=1,T=nn;
		int ans=g.Maxflow(S,T);
		if(ans>=c) cout<<"possible"<<endl;
		else{
			vector<int>cut=g.Mincut();
			vector<Edge>re;
			g.Reduce();
			for(int i=0;i<cut.size();i++){
				Edge& e=g.edges[cut[i]];
				int temp=e.cap;
				e.cap=c;
				g.ClearFlow();
				if(ans+g.Maxflow(S,T)>=c) re.pb(e);
				e.cap=temp; 
			}
			if(re.size()==0) cout<<"not possible"<<endl;
			else{
				sort(re.begin(),re.end(),cmp);
				for(int i=0;i<re.size();i++){
					if(i==0) cout<<"possible option:("<<re[i].from<<","<<re[i].to<<")";
					else cout<<",("<<re[i].from<<","<<re[i].to<<")";
				}
				cout<<endl;
			}
		}
	}
	return 0;
}

思路

先跑一次最大流，最大流如果大于等于C，就不用括弧了
如果不行的话，就进行括弧。
扩大哪些弧的容量呢。答案是割边的容量，因为最小割==最大流
我们先找出所有的割边，如何找割边呢，如果是dinic算法的话，就找到vis[u] == true 而vis[v] == false 且该边容量大于0的边，这些边就是割边了
接着将割边一条一条的扩容，只需要扩大到C的容量就可以了，然后在残余网络上跑最大流就可以了
还有一个问题是怎么求残余网络，只需要将所有边的容量减去流量就是残余网络了
加上2个优化：第一个优化是求完最大流后把流量留着 以后每次在它的基础上增广
第二个优化是每次没必要求出最大流 增广到流量至少为C时就停下来

LA 2957

题目要求

宇宙中有n个星球 你的任务是用最短的时间把k个超级计算机从星球S运送到星球T 每个超级计算机需要一整艘飞船来运输
行星之间有m条双向隧道 每条隧道需要一天时间来通过 且不能有两艘飞船同时使用同一条隧道 隧道不会连接两个相同的
行星 且每一对行星之间最多只有一条隧道
蓝书P368

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 2550
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
struct Edge{
  int from, to, cap, flow;
};
struct Dinic{
  int n, m, s, t;
  vector<Edge> edges;   
  vector<int> G[maxn];   
  bool vis[maxn];         
  int d[maxn];           
  int cur[maxn];       
void clearNodes(int a, int b){
    for(int i = a; i <= b; i++) G[i].clear();
}
void init(){ edges.clear();}
void AddEdge(int from, int to, int cap){
    edges.push_back((Edge){from, to, cap, 0});
    edges.push_back((Edge){to, from, 0, 0});
    m = edges.size();
    G[from].push_back(m-2);
    G[to].push_back(m-1);
}
bool BFS(){
    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    Q.push(s);
    vis[s] = 1;
    d[s] = 0;
    while(!Q.empty()) {
      int x = Q.front(); Q.pop();
      for(int i = 0; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i]];
        if(!vis[e.to] && e.cap > e.flow) {
          vis[e.to] = 1;
          d[e.to] = d[x] + 1;
          Q.push(e.to);
        }
      }
    }
    return vis[t];
}
int DFS(int x, int a){
    if(x == t || a == 0) return a;
    int flow = 0, f;
    for(int& i = cur[x]; i < G[x].size(); i++) {
      Edge& e = edges[G[x][i]];
      if(d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > 0) {
        e.flow += f;
        edges[G[x][i]^1].flow -= f;
        flow += f;
        a -= f;
        if(a == 0) break;
      }
    }
    return flow;
}
int Maxflow(int s, int t,int limit){
    this->s = s; this->t = t;
    int flow = 0;
    while(BFS()) {
      memset(cur, 0, sizeof(cur));
      flow += DFS(s, limit-flow);
      if(flow==limit) break;
    }
    return flow;
}
}g;
const int maxm=210;
int u[maxm],v[maxm];
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n,m,S,T,k;
	while(cin>>n>>m>>k>>S>>T){
		if(n==0 && m==0 && k==0 && S==0 && T==0) break;
		for(int i=0;i<m;i++) cin>>u[i]>>v[i];
		g.init();
		g.clearNodes(0,n-1);
		int day=1;
		int flow=0;
		for(;;){
			g.clearNodes(day*n,day*n+n-1);
			for(int i=0;i<n;i++) g.AddEdge((day-1)*n+i,day*n+i,inf);
			for(int i=0;i<m;i++){
				g.AddEdge((day-1)*n+u[i]-1,day*n+v[i]-1,1);
				g.AddEdge((day-1)*n+v[i]-1,day*n+u[i]-1,1);
			}
			flow+=g.Maxflow(S-1,day*n+T-1,k-flow);
			if(flow==k) break;
			day++;
		}
		cout<<day<<endl;
		int idx=0;
		vector<int>location(k,S);
		for(int i=1;i<=day;i++){
			idx+=2*n;
			vector<int>move(k,0);
			vector<int>a,b;
			vector<pii>pi;
			for(int i=0;i<m;i++){
				int f1=g.edges[idx].flow; idx+=2;
				int f2=g.edges[idx].flow; idx+=2;
				if(f1==1 && f2==0) { a.pb(u[i]); b.pb(v[i]); }
				if(f2==1 && f1==0) { a.pb(v[i]); b.pb(u[i]); }
			}
			cout<<a.size();
			for(int i=0;i<a.size();i++){
				for(int j=0;j<k;j++){
					if(!move[j] && location[j]==a[i]){
						pi.pb(mp(j+1,b[i]));
						move[j]=1;
						location[j]=b[i];
						break;
					}
				}
			}
			sort(pi.begin(),pi.end());
			for(int i=0;i<pi.size();i++) cout<<" "<<pi[i].fi<<" "<<pi[i].se;
			cout<<endl;
		}
	}
	return 0;
}

思路

蓝书P368
注意点：
第一天的点编号为0->n-1
对于i+1天 清空后与第i天建边
为满足流恰好等于k 每次在原有最大流的基础上增广 设置一个limit=k-flow 每次增广剩下的流量
对于Maxflow函数中 同样为确保流量尽可能等于limit又不超过limit 每次增广limit-flow的流量
对于输出解 idx初始值=2*n是为了跳过原地不动的点 对于每个u[i]和v[i] 其实建边了四次 正向2次 反向2次
所以idx+2实际上是判断u[i]->v[i]和v[i]->u[i]的流量 如果前驱flow==1后驱flow==0 存入a和b 反向同理
最后对于每一天遍历满足条件a边的大小和k个计算机 如果该计算机未走动过(move[j]==0)并且此时它的位置在a[i]处 存入pi排序输出

LA 2531

题目要求

有n支队伍进行比赛 每支队伍需要打的比赛数目相同 每场比赛恰好有一支队伍胜 另一只队伍负 给出每支队伍目前胜的场数和败的场数 以及
每两个队伍还剩下的比赛场数 确定所有可能得冠军的球队(获胜场数最多的得冠军 可以并列)
蓝书P369

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 700
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int n;
struct Edge{
  int from, to, cap, flow;
};
struct Dinic{
  int n, m, s, t;
  vector<Edge> edges;   
  vector<int> G[maxn];   
  bool vis[maxn];         
  int d[maxn];           
  int cur[maxn];       
void ClearAll(int n){
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
}
void AddEdge(int from, int to, int cap){
    edges.push_back((Edge){from, to, cap, 0});
    edges.push_back((Edge){to, from, 0, 0});
    m = edges.size();
    G[from].push_back(m-2);
    G[to].push_back(m-1);
}
bool BFS(){
    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    Q.push(s);
    vis[s] = 1;
    d[s] = 0;
    while(!Q.empty()) {
      int x = Q.front(); Q.pop();
      for(int i = 0; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i]];
        if(!vis[e.to] && e.cap > e.flow) {
          vis[e.to] = 1;
          d[e.to] = d[x] + 1;
          Q.push(e.to);
        }
      }
    }
    return vis[t];
}
int DFS(int x, int a){
    if(x == t || a == 0) return a;
    int flow = 0, f;
    for(int& i = cur[x]; i < G[x].size(); i++) {
      Edge& e = edges[G[x][i]];
      if(d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > 0) {
        e.flow += f;
        edges[G[x][i]^1].flow -= f;
        flow += f;
        a -= f;
        if(a == 0) break;
      }
    }
    return flow;
}
int Maxflow(int s, int t){
    this->s = s; this->t = t;
    int flow = 0;
    while(BFS()) {
      memset(cur, 0, sizeof(cur));
      flow += DFS(s, inf);
    }
    return flow;
}
}g;
const int maxm=25+5;
int a[maxm][maxm],w[maxm],d[maxm];
int ID(int u,int v){ return n*u+v; }
int ID(int u){ return n*n+u; }
bool canWin(int team){
	int total=w[team];
	for(int i=0;i<n;i++) total+=a[team][i];  // 计算team全胜后的总胜利场数
	for(int i=0;i<n;i++) if(w[i]>total) return false;
	g.ClearAll(maxn);
	int full=0;
	int s=0,t=n*n+n+1;  // 构图。s=0, 结点(u,v)的编号为u*n+v 结点u的编号为n^2+u+1, t=n^2+n
	for(int u=0;u<n;u++){
		for(int v=u+1;v<n;v++){
			if(a[u][v]>0) g.AddEdge(s,ID(u,v),a[u][v]);  // S到(u,v)的弧
			full+=a[u][v];
			g.AddEdge(ID(u,v),ID(u),inf);  // (u,v)到u的弧
			g.AddEdge(ID(u,v),ID(v),inf);  // (u,v)到v的弧
		}
		if(total-w[u]>0) g.AddEdge(ID(u),t,total-w[u]);  // u到T的弧
	}
	return g.Maxflow(s,t)==full;
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=0;i<n;i++) cin>>w[i]>>d[i];
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++) cin>>a[i][j];
		}
		bool first=true;
		for(int i=0;i<n;i++){
			if(canWin(i)){
				if(first) first=false;
				else cout<<" ";
				cout<<i+1;
			}
		}
		cout<<endl;
	}
	return 0;
}

思路

见注释
蓝书P369

本文标题:网络流拓展二

文章作者:Hippopmonkey

发布时间:2017-07-19, 15:07:11

最后更新:2017-09-13, 20:26:25

原始链接:http://xuboming8.github.io/2017/07/19/网络流拓展二/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 网络流拓展二
    1. 1.1. POJ 3680(区间k覆盖问题+离散)
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. HDU 4106(区间k覆盖变形)
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. POJ 3762(同3680)
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. POJ 3422(区间累计k覆盖最大值)
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. HDU 3667(费用与流量平方)
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. UVA 11613(流量不固定s-t最小费用流)
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路
    7. 1.7. LA 3231(公平分配问题)
      1. 1.7.1. 题目要求
      2. 1.7.2. 参考AC代码
      3. 1.7.3. 思路
    8. 1.8. ZOJ 2587(最小割唯一判断)
      1. 1.8.1. 题目要求
      2. 1.8.2. 参考AC代码
      3. 1.8.3. 思路
    9. 1.9. UVA 11248(扩弧)
      1. 1.9.1. 题目要求
      2. 1.9.2. 参考AC代码
      3. 1.9.3. 思路
    10. 1.10. LA 2957
      1. 1.10.1. 题目要求
      2. 1.10.2. 参考AC代码
      3. 1.10.3. 思路
    11. 1.11. LA 2531
      1. 1.11.1. 题目要求
      2. 1.11.2. 参考AC代码
      3. 1.11.3. 思路
|