网络流拓展三

自用笔记算法

网络流拓展三

总结有关拆点拆边

拆点：
1.结点有最大容量 拆点构造流量
2.结点只能经过一次 拆点加流量1
3.结点存在多种状态 例如构造每一天的状态
4.迷宫k覆盖问题
拆边：
某条边存在第一次经过和以后经过的状态不一样
例如第一天的权值和后面的权值不同 或者迷宫的点权只能取一次

2017新疆网赛J(拆点)

转跳链接

HDU 6118(流量不固定s-t最小流)

转跳链接

uva 10779

题目要求

蓝书P370

参考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
#include<bits/stdc++.h>
#define maxn 100
#define inf 0x3f3f3f3f 
#define mm(a,b) memset(a,b,sizeof(a))
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];       
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;
int hashh[15][30];
int flag=1;
int main(){
//	freopen("input.txt","r",stdin);
	int t;
	scanf("%d",&t);
	while(t--){
		printf("Case #%d: ",flag++);
		int n,m;
		scanf("%d%d",&n,&m);
		int S=0,T=n+m;
		mm(hashh,0);
		g.ClearAll(maxn);
		for(int i=1;i<=n;i++){
			int k;
			scanf("%d",&k);
			while(k--){
				int x; scanf("%d",&x);
				hashh[i][x]++;
			}
		}
		for(int i=1;i<=m;i++){
			g.AddEdge(i,T,1);
			if(hashh[1][i]) g.AddEdge(S,i,hashh[1][i]);
		}
		for(int i=2;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(hashh[i][j]==1) continue;
				if(hashh[i][j]==0) g.AddEdge(j,i+n-1,1);
				if(hashh[i][j]>=2) g.AddEdge(i+n-1,j,hashh[i][j]-1);
			}
		}
		int ans=g.Maxflow(S,T);
		printf("%d\n",ans);
	}
	return 0;
}

思路

建图见蓝书P370-371
注意编号2-n的人拥有卡片数量为1的时候不执行任何操作

poj 3436

题目要求

有N台组装电脑的机器 每台电脑的组成有P部分。
每台机器有P个输入输出规格 还有一个最大容量Q(以每小时为单位)
其中输入规格有三种情况：0,1,2
0：该部分不能存在
1：该部分必须存在
2：该部分可有可无
输出规格有2种情况：0,1
0：该部分不存在
1：该部分存在
只有满足输入规则 该电脑才能进入机器加工 加工后的输出部分按照输出规则给出
求生产电脑最大的台数 以及加工的总次数
对于每次加工 输出由机器a到机器b 每小时输出了多少台电脑

参考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
#include<bits/stdc++.h>
#define maxn 200
#define inf 0x3f3f3f3f 
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,p;
bool isStart(int x[]){
    for(int i=0;i<p;i++){
        if(x[i]==1) return false;
    }
    return true;
}
bool isEnd(int x[]){
    for(int i=0;i<p;i++){
        if(x[i]==0) return false;
    }
    return true;
}
bool isInAndOut(int in[],int out[]){
    for(int i=0;i<p;i++){
        if(out[i]!=in[i]&&in[i]!=2) return false;
    }
    return true;
}
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;
int w[55],in[55][15],out[55][15];
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d",&p,&n)!=EOF){
		g.ClearAll(maxn);
		int S=0,T=2*n+1;
		for(int i=1;i<=n;i++){
			scanf("%d",&w[i]);
			for(int j=0;j<p;j++) scanf("%d",&in[i][j]);
			for(int j=0;j<p;j++) scanf("%d",&out[i][j]);
			if(isStart(in[i])) g.AddEdge(S,i,inf);
			if(isEnd(out[i])) g.AddEdge(i+n,T,inf);
		}
		for(int i=1;i<=n;i++) g.AddEdge(i,i+n,w[i]);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i==j) continue;
				if(isInAndOut(in[j],out[i])) g.AddEdge(i+n,j,inf);
			}
		}
		int ans=g.Maxflow(S,T);
		int num=0;
		for(int i=0;i<g.edges.size();i++){
			if(g.edges[i].from==S || g.edges[i].to==S || g.edges[i].from==T || g.edges[i].to==T) continue;
			if(g.edges[i].to==g.edges[i].from+n || g.edges[i].to==g.edges[i].from-n) continue;
			if(g.edges[i].flow<0) num++;
		}
		printf("%d %d\n",ans,num);
		for(int i=0;i<g.edges.size();i++){
			if(g.edges[i].from==S || g.edges[i].to==S || g.edges[i].from==T || g.edges[i].to==T) continue;
			if(g.edges[i].to==g.edges[i].from+n || g.edges[i].to==g.edges[i].from-n) continue;
			if(g.edges[i].flow<0) printf("%d %d %d\n",g.edges[i].to-n,g.edges[i].from,-g.edges[i].flow);
		}
	}
	return 0;
}

思路

建图:
首先对于每台机器都有一个容量 所以拆点 i到i+n 容量为w[i]
由S到i建边：由于刚开始的S为空 所以输入格式不能有1 若有不能建边 其余均由S连向i 容量为inf
有i+n到T建边：若输出的格式中均为1 那么建边 否则不能建边
若有某台机器的输出满足另一台机器的输出 那么两台机器建边 容量为inf
跑一遍dinic就可以求出最大流
这里对num和路径的输出判断是根据反向边来判断 由于反向边存储时flow=0 所以flow<0代表这条路径有流量经过
输出注意由于边是反向 颠倒位置输出即可

poj 1087

题目要求

题目大意：
在这个题目里有两种物品，一个是插座，一个是电器
插座只有一个插孔和一个插头，电器只有一个插头
首先有n种插座，n种插座用字符串表示，这n种插座可以理解为是插在电源上的插座
然后有m个电器，现在电器要充电，电器用字符串表示，每个电器都有自己可以插的插座
(这个插座可以不是那n个插在电源上的插座，可以是其他的插座)
现在有k个信息
s1 s2代表s1插座可以插到s2插座上去，这里类似于将插头转换了一下
这些s1与s2也可以不是那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
#include<bits/stdc++.h>
#define maxn 350
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
map<string,int>mp1,mp2;
int n,m,k;
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;
char op[30];
char op1[30],op2[30];
int cnt;
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d",&n)!=EOF){
		mp1.clear(),mp2.clear();
		cnt=0;
		g.ClearAll(maxn);
		int S=0,T=310;
		for(int i=1;i<=n;i++){
			scanf("%s",op);
			mp1[op]=++cnt;
			g.AddEdge(cnt,T,1);
		}
		scanf("%d",&m);
		for(int i=1;i<=m;i++){
			scanf("%s %s",op1,op2);
			mp2[op1]=++cnt;
			g.AddEdge(S,cnt,1);
			if(mp1.count(op2)) g.AddEdge(mp2[op1],mp1[op2],1);
			else{
				mp1[op2]=++cnt;
				g.AddEdge(mp2[op1],mp1[op2],1);
			}
		}
		scanf("%d",&k);
		while(k--){
			scanf("%s %s",op1,op2);
			g.AddEdge(mp1[op1],mp1[op2],inf);
		}
		int ans=g.Maxflow(S,T);
		printf("%d\n",m-ans);
	}
	return 0;
}

思路

建一个源点，指向所有电器，容量为1
所有电器指向他们可以插的那个插头上，容量为1
如果一个插头可以插到另一个插头，那么将s1指向s2，容量为无限大
将所有插在电源上的插头指向汇点，容量为1
注意点：
1.电器连向的插座可能超过n的范围 需要重新给该点计数
2.新加的插座不能连向T 他们只启到转换的作用
3.没有考虑k中的插座可能是新加的 但也过了 所以k中新加的插座在m种电器中必定出现过
4.注意数组大小至少开301

poj 3281

题目要求

有N头牛，F个食物，D个饮料。
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
#include<bits/stdc++.h>
#define maxn 550
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
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];       
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;
int n,f,d;
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d%d",&n,&f,&d)!=EOF){
		int S=0,T=f+2*n+d+1;
		g.ClearAll(maxn);
		for(int i=1;i<=f;i++) g.AddEdge(S,i,1);
		for(int i=1;i<=d;i++) g.AddEdge(i+f+2*n,T,1);
		for(int i=1;i<=n;i++) g.AddEdge(i+f,i+f+n,1);
		for(int i=1;i<=n;i++){
			int num1,num2;
			scanf("%d%d",&num1,&num2);
			for(int j=1;j<=num1;j++){
				int x;
				scanf("%d",&x);
				g.AddEdge(x,i+f,1);
			}	
			for(int j=1;j<=num2;j++){
				int x;
				scanf("%d",&x);
				g.AddEdge(i+f+n,x+f+2*n,1);
			}
		}
		int ans=g.Maxflow(S,T);
		printf("%d\n",ans);
	}
	return 0;
}

思路

最大流建图是把食物和饮料放在两端。一头牛拆分成两个点，两点之间的容量为1.喜欢的食物和饮料跟牛建条边，容量为1.
加个源点和汇点。源点与食物、饮料和汇点的边容量都是1，表示每种食物和饮料只有一个。
注意：本题的牛由于只能经过一次(一个食物或者饮料只能给一头牛 一头牛只能获得一个食物或者饮料) 所以需要拆点 容量为1

poj 2516

题目要求

有n个商店，k种物品和m个供货商，让你求进满足商店需求的货物的最小花费？
输入n,k,m
然后是一个n×k的矩阵，n个商店对每种货物的需求，表示第i个商店需要第j种货物x个
然后是m×k的矩阵，m个供货商可以供k种货物的数量，表示第i个供货商 提供第j中货物x个
接下来是k个n×m的矩阵，表示第i个货物，由k供应商发货给j商店的价格x

参考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
#include<bits/stdc++.h>
#define maxn 200
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,m,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;
	}
	int Mincost(int s,int t){
		int flow=0,cost=0;
		while(BellmanFord(s,t,flow,cost));
		return cost;
	}
}mc;
int g1[55][55],g2[55][55];
int need[55],sup[55];
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d%d",&n,&m,&k)!=EOF){
		if(n==0 && m==0 && k==0) continue;
		mm(need,0),mm(sup,0),mm(g1,0),mm(g2,0);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=k;j++) scanf("%d",&g1[i][j]),need[j]+=g1[i][j];
		}
		for(int i=1;i<=m;i++){
			for(int j=1;j<=k;j++) scanf("%d",&g2[i][j]),sup[j]+=g2[i][j];
		}
		int flag=1,ans=0;
		for(int i=1;i<=k;i++){
			mc.init(maxn);
			int S=0,T=n+m+1;
			for(int j=1;j<=n;j++) mc.AddEdge(S,j,g1[j][i],0);
			for(int j=1;j<=m;j++) mc.AddEdge(j+n,T,g2[j][i],0);
			for(int j=1;j<=n;j++){
				for(int p=1;p<=m;p++){
					int x;
					scanf("%d",&x);
					mc.AddEdge(j,p+n,inf,x);
				}
			}
			if(need[i]>sup[i]) flag=0;
			if(flag) ans+=mc.Mincost(S,T);
		}
		if(flag) printf("%d\n",ans);
		else puts("-1");
	}
	return 0;
}

思路

最小费用最大流
常规解法需要拆点 把每个商品拆成n个点 代表每个供应商提供该物品给每个商店的价格 据说会超时
优化解法：每个满足条件的物品都跑一次mcmf
need为物品i的需求 sup为物品i的供给
对于第k个物品 若需求大于供给 flag置0输出-1
否则建图 s到每个商店 容量为这个商店需要第i个物品的数量 费用为0
每个供应商到t 容量为这个供应商提供第i个物品的数量 费用为0
商店到供应商利用第k个矩阵建图(在for循环里输入 可以避免开三维数组) 容量为inf 费用为第该供应商提供该物品到该商店的价格x
若所有商品都满足条件 ans加上所有的mcmf就是所求

poj 1459

题目要求

简单的说下题意（按输入输出来讲，前面的描述一堆的rubbish，还用来误导人），给你n个点，其中有np个是能提供电力的点，nc个是能消费电力的点，
剩下的点(n-np-nc)是中转战即不提供电力也不消费电力，点与点之间是有线路存在的，有m条线路，每条线路有最多运载限定。
前4个数据就是有n个点，np个供电点,nc个消费点,m条线路，接来题目先给出的是m条线路的数据，(起点,终点)最多运载量,
然后是np个供电点的数据(供电点)最多供电量，接着就是nc个消费点的数据(消费点)最多消费电量。
题目要我们求出给定的图最大能消费的总电量（就是求最大流）

参考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
#include<bits/stdc++.h>
#define maxn 200
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
char op;
int n,m,np,nc;
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;
int main(){
//  freopen("input.txt","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  while(cin>>n>>np>>nc>>m){
    g.ClearAll(maxn);
    for(int i=1;i<=m;i++){
      int u,v,w;
      cin>>op>>u>>op>>v>>op>>w;
      g.AddEdge(u,v,w);
    }
    int S=n,T=n+1;
    for(int i=1;i<=np;i++){
      int x,w;
      cin>>op>>x>>op>>w;
      g.AddEdge(S,x,w);
    }
    for(int i=1;i<=nc;i++){
      int x,w;
      cin>>op>>x>>op>>w;
      g.AddEdge(x,T,w);
    }
    int ans=g.Maxflow(S,T);
    cout<<ans<<endl;
  }
  return 0;
}

思路

多源多汇水题
建超级源点和超级汇点 np供电和S连 nc耗电和T连 m条路径相连 跑最大流
注意：
1.点的下标从0开始
2.题目输入有坑 每个括号前可以有任意多个空格 对cin没影响但是对scanf有影响
3.op是多余的条件

HDU 4292

题目要求

等价poj3281

参考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
#include<bits/stdc++.h>
#define maxn 1000
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,f,d;
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;
char op[250];
int main(){
//  freopen("input.txt","r",stdin);
  while(scanf("%d%d%d",&n,&f,&d)!=EOF){
    g.ClearAll(maxn);
    int S=0,T=2*n+f+d+1;
    for(int i=1;i<=f;i++){
      int x;
      scanf("%d",&x);
      g.AddEdge(S,i,x);
    }
    for(int i=1;i<=d;i++){
      int x;
      scanf("%d",&x);
      g.AddEdge(i+f+2*n,T,x);
    }
    for(int i=1;i<=n;i++) g.AddEdge(i+f,i+f+n,1);
    for(int i=1;i<=n;i++){
      scanf("%s",op+1);
      for(int j=1;j<=f;j++){
        if(op[j]=='Y') g.AddEdge(j,i+f,1);
      }
    }
    for(int i=1;i<=n;i++){
      scanf("%s",op+1);
      for(int j=1;j<=d;j++){
        if(op[j]=='Y') g.AddEdge(i+f+n,j+f+2*n,1);
      }
    }
    int ans=g.Maxflow(S,T);
    printf("%d\n",ans);
  }
  return 0;
}

思路

见poj3281思路
区别在于本题每种食物和饮料都有一定的数量 cap为x即可

HDU 4289

题目要求

给一张无向图 n点m边 有源点S和汇点T 删除每个点需要一个点权 问破坏S到T的连通性的最小的花费是多少

参考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
#include<bits/stdc++.h>
#define maxn 500
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,m;
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;
int main(){
//  freopen("input.txt","r",stdin);
  while(scanf("%d%d",&n,&m)!=EOF){
    g.ClearAll(maxn);
    int S,T;
    scanf("%d%d",&S,&T);
    T+=n;
    for(int i=1;i<=n;i++){
      int x;
      scanf("%d",&x);
      g.AddEdge(i,i+n,x);
    }
    for(int i=1;i<=m;i++){
      int u,v;
      scanf("%d%d",&u,&v);
      g.AddEdge(u+n,v,inf);
      g.AddEdge(v+n,u,inf);
    }
    int ans=g.Maxflow(S,T);
    printf("%d\n",ans);
  }
  return 0;
}

思路

等价于最小割 所以跑最大流 注意建图
拆点 i到i+n是该点的点权 u到v的双向边建成u+n到v和v+n到u 容量为inf 因为都是从右边的点寻找下一个城市
跑一遍最大流就是所求

本文标题:网络流拓展三

文章作者:Hippopmonkey

发布时间:2017-09-13, 20:19:08

最后更新:2017-09-19, 17:25:59

原始链接:http://xuboming8.github.io/2017/09/13/网络流拓展三/

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

文章目录
  1. 1. 网络流拓展三
    1. 1.1. 总结有关拆点拆边
    2. 1.2. 2017新疆网赛J(拆点)
    3. 1.3. HDU 6118(流量不固定s-t最小流)
    4. 1.4. uva 10779
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. poj 3436
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. poj 1087
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路
    7. 1.7. poj 3281
      1. 1.7.1. 题目要求
      2. 1.7.2. 参考AC代码
      3. 1.7.3. 思路
    8. 1.8. poj 2516
      1. 1.8.1. 题目要求
      2. 1.8.2. 参考AC代码
      3. 1.8.3. 思路
    9. 1.9. poj 1459
      1. 1.9.1. 题目要求
      2. 1.9.2. 参考AC代码
      3. 1.9.3. 思路
    10. 1.10. HDU 4292
      1. 1.10.1. 题目要求
      2. 1.10.2. 参考AC代码
      3. 1.10.3. 思路
    11. 1.11. HDU 4289
      1. 1.11.1. 题目要求
      2. 1.11.2. 参考AC代码
      3. 1.11.3. 思路
|