网络流拓展四

自用笔记算法

网络流拓展四

HDU 3081

题目要求

有N个女孩要与N个男孩玩配对游戏.每个女孩有一个可选男孩的集合(即该女孩可以选自己集合中的任意一个男孩作为该轮的搭档).
然后从第一轮开始,每个女孩都要和一个不同的男孩配对.如果第一轮N个女孩都配对成功,那么就开始第二轮配对,女孩依然从自己的备选男孩集合中选择,
但是不能选那些已经被该女孩在前几轮选择中选过的男孩了(比如i女孩在第一轮选了j男孩,那么i在第二轮就不能选j男孩了). 问你游戏最多能进行多少轮?
给出女孩可以选择男孩的关系和女孩是朋友之间的关系
如果女孩a和女孩b是朋友并且a能选c 那么b也可以选c

参考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
#include<bits/stdc++.h>
#define maxn 400
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int t,n,m,f;
int mp[105][105];
int p[maxn];
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 find(int x){
	return p[x]==x?x:p[x]=find(p[x]);
}
void merge(int u,int v){
	int x=find(u),y=find(v);
	if(x!=y) p[x]=y; 
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&n,&m,&f);
		int S=0,T=2*n+1;
		mm(mp,0);
		for(int i=0;i<=400;i++) p[i]=i; 
		for(int i=1;i<=m;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			mp[u][v]=1;
		}
		for(int i=1;i<=f;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			merge(u,v);
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(find(i)==find(j)){
					for(int k=1;k<=n;k++) mp[i][k]=mp[j][k]=(mp[i][k] || mp[j][k]);
				}
			}
		}
		int l=0,r=100,ans=0;
		while(l<=r){
			int mid=l+r>>1;
			g.ClearAll(maxn);
			for(int i=1;i<=n;i++) g.AddEdge(S,i,mid);
			for(int i=1;i<=n;i++) g.AddEdge(i+n,T,mid);
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					if(mp[i][j]) g.AddEdge(i,j+n,1);
				}
			}
			int mxflow=g.Maxflow(S,T);
			if(mxflow==mid*n){
				ans=mid;
				l=mid+1;
			}
			else r=mid-1;
		}
		printf("%d\n",ans);
	}
	return 0;
}

参考AC代码(floyd传递闭包)

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 400
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int t,n,m,f;
int mp[105][105];
int bag[105][105];
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);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&n,&m,&f);
		int S=0,T=2*n+1;
		mm(mp,0),mm(bag,0);
		for(int i=1;i<=m;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			mp[u][v]=1;
		}
		for(int i=1;i<=f;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			bag[u][v]=bag[v][u]=1;
		}
		for(int k=1;k<=n;k++){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					bag[i][j]=bag[i][j]||(bag[i][k]&&bag[k][j]);
				}
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(bag[i][j]){
					for(int k=1;k<=n;k++){
						mp[i][k]=mp[j][k]=(mp[i][k] || mp[j][k]);
					}
				}
			}
		}
		int l=0,r=100,ans=0;
		while(l<=r){
			int mid=l+r>>1;
			g.ClearAll(maxn);
			for(int i=1;i<=n;i++) g.AddEdge(S,i,mid);
			for(int i=1;i<=n;i++) g.AddEdge(i+n,T,mid);
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					if(mp[i][j]) g.AddEdge(i,j+n,1);
				}
			}
			int mxflow=g.Maxflow(S,T);
			if(mxflow==mid*n){
				ans=mid;
				l=mid+1;
			}
			else r=mid-1;
		}
		printf("%d\n",ans);
	}
	return 0;
}

思路

二分最大流+并查集(floyd传递闭包)
源点s为0,汇点t为2×n+1.女孩编号1到n,男孩编号n+1到2×n. 假设我们当前二分尝试的轮数为K(即能够进行K轮匹配):
首先如果女孩i可能选择男孩j,那么就有边(i,j+n,1).且源点到每个女孩i有边(s,i,K),每个男孩j到汇点t有边(j+n,t,K).
如果最大流==K×n,那么就表示可以进行最少K轮匹配.
通过并查集或者传递闭包的方式传递所有朋友关系的女生对男生的选择

HDU 3416

题目要求

有n个城市，m条边，a到b耗费为c，为单向边。要求从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
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
146
147
148
#include<bits/stdc++.h>
#define maxn 2050
#define maxm 200050
#define inf 0x3f3f3f3f 
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
struct Edge1 {
  int from, to, dist;
};
struct HeapNode {
  int d, u;
  bool operator < (const HeapNode& rhs) const {
    return d > rhs.d;
  }
};
struct Dijkstra {
  int n, m;
  vector<Edge1> edges;
  vector<int> G[maxn];
  bool done[maxn];    // 是否已永久标号
  int d[maxn];        // s到各个点的距离
  int p[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 dist) {
    edges.push_back((Edge1){from, to, dist});
    m = edges.size();
    G[from].push_back(m-1);
  }
  void dijkstra(int s) {
    priority_queue<HeapNode> Q;
    for(int i = 0; i < n; i++) d[i] = inf;
    d[s] = 0;
    memset(done, 0, sizeof(done));
    Q.push((HeapNode){0, s});
    while(!Q.empty()) {
      HeapNode x = Q.top(); Q.pop();
      int u = x.u;
      if(done[u]) continue;
      done[u] = true;
      for(int i = 0; i < G[u].size(); i++) {
        Edge1& e = edges[G[u][i]];
        if(d[e.to] > d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          Q.push((HeapNode){d[e.to], e.to});
        }
      }
    }
  }
}dj;
struct Edge2{
  int from, to, cap, flow;
};
struct Dinic{
  int n, m, s, t;
  vector<Edge2> 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((Edge2){from, to, cap, 0});
    edges.push_back((Edge2){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++) {
        Edge2& 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++) {
      Edge2& 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 d1[maxn],d2[maxn]; 
int u[maxm],v[maxm],w[maxm];
int S,T;
int main(){
//	freopen("input.txt","r",stdin);
	int t;
	scanf("%d",&t);
	while(t--){
		int n,m;
		scanf("%d%d",&n,&m);
		dj.init(maxn);
		for(int i=1;i<=m;i++) scanf("%d%d%d",&u[i],&v[i],&w[i]);
		scanf("%d%d",&S,&T);
		mm(d1,0),mm(d2,0);
		dj.init(maxn);
		for(int i=1;i<=m;i++) dj.AddEdge(u[i],v[i],w[i]);
		dj.dijkstra(S); memcpy(d1,dj.d,sizeof(dj.d));
		dj.init(maxn);
		for(int i=1;i<=m;i++) dj.AddEdge(v[i],u[i],w[i]);
		dj.dijkstra(T); memcpy(d2,dj.d,sizeof(dj.d));
		g.ClearAll(maxn);
		for(int i=1;i<=m;i++){
			if(d1[u[i]]+d2[v[i]]+w[i]==d1[T]) g.AddEdge(u[i],v[i],1);
		}
		int ans=g.Maxflow(S,T);
		printf("%d\n",ans);
	}
	return 0;
}

思路

先跑2遍最短路 记录下s出发的最短路d1 t出发的最短路d2 注意由于是单向边 计算d2的时候加入的是反向边
对于一个u->v的有向边 若d1[u]+d2[v]+w[i]就是s到t的最短路 那么这条变就是最短路上的一条边 加入的网络流构图中 流量为1
这样跑一遍最大流就可以求出每个点只经过一次的最短路个数
注意uvw的数组大小

HDU 3277

题目要求

在HDU 3081的基础上多了一个条件：
女孩除了能选自己喜欢的男孩外还能选任意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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<bits/stdc++.h>
#define maxn 1000
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,m,k,f;
int p[maxn];
int mp[300][300];
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 find(int x){
	return p[x]==x?x:p[x]=find(p[x]);
}
void merge(int u,int v){
	int x=find(u),y=find(v);
	if(x!=y) p[x]=y;
}
bool same(int x,int y){
	return find(x)==find(y);
}
int main(){
//	freopen("input.txt","r",stdin);
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d%d",&n,&m,&k,&f);
		mm(mp,0);
		for(int i=0;i<maxn;i++) p[i]=i;
		int S=0,T=3*n+1;
		for(int i=1;i<=m;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			mp[u][v]=1;
		}
		for(int i=1;i<=f;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			merge(u,v);
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(same(i,j)){
					for(int k=1;k<=n;k++){
						mp[i][k]=mp[j][k]=(mp[i][k]||mp[j][k]);
					}
				}
			}
		}
		int l=0,r=250,ans=0;
		while(l<=r){
			g.ClearAll(maxn); 
			int mid=l+r>>1;
			for(int i=1;i<=n;i++){
				g.AddEdge(S,i,mid);
				g.AddEdge(i+2*n,T,mid);
				g.AddEdge(i,i+n,k);
			}
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					if(mp[i][j]) g.AddEdge(i,j+2*n,1);
					else g.AddEdge(i+n,j+2*n,1);
				}
			}
			int mxflow=g.Maxflow(S,T);
			if(mxflow==n*mid){
				ans=mid;
				l=mid+1;
			}
			else r=mid-1;
			
		}
		printf("%d\n",ans);
	}
	return 0;
}

思路

假设当前我们二分轮数为limit 源点s编号0 女孩i分成两个点i和i+n编号(编号i的点用来连接该女孩喜欢的男孩,编号为i+n的点用来连接该女孩不喜欢的男孩)
男孩编号为2n+1到2n+n, 汇点t编号为3n+1.
首先源点s到第i个女孩有边(s, i, limit)
第i个女孩的i点到i+n点有边(i, i+n, k)
如果第i个女孩可以选男孩j,那么有边(i, j, 1). 否则有边(i+n, j, 1)
每个男孩j到汇点t有边(j, t, limit)
最终看max_flow是否==limit*n 即可.
并查集使用同理

uva 10480

题目要求

要求在最小费用的前提下切断点1和点2的连通性 问要切断哪些割边 输出割边的端点编号

参考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;
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;
}
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;
}
}g;
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d",&n,&m)!=EOF){
		if(n==0 && m==0) break;
		g.ClearAll(maxn);
		for(int i=1;i<=m;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			g.AddEdge(u,v,w);
			g.AddEdge(v,u,w);
		}
		int S=1,T=2;
		g.Maxflow(S,T);
		vector<int>ans=g.Mincut();
		for(auto p:ans){
			printf("%d %d\n",g.edges[p].from,g.edges[p].to);
		}
		printf("\n");
	}
	return 0;
}

思路

用打印割边的模版(满流的边)
打印即可

HDU 2732

题目要求

给你一个网格,网格上的一些位置上有一只蜥蜴,所有蜥蜴的最大跳跃距离是d,如果一只蜥蜴能跳出网格边缘,那么它就安全了.
且每个网格有一个最大跳出次数x,即最多有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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
#define maxn 1000
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int t,n,m,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 s[30];
int Case=1;
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&d);
		g.ClearAll(maxn);
		int sum=0;
		int S=0,T=900;
		for(int i=1;i<=n;i++){
			scanf("%s",s+1);
			m=strlen(s+1);
			for(int j=1;j<=m;j++){
				if(s[j]=='0') continue;
				int index1=(i-1)*m+j;
				g.AddEdge(index1,index1+n*m,s[j]-'0');
				if(i<=d || i+d>n || j<=d || j+d>m) g.AddEdge(index1+n*m,T,inf);
				else{
					for(int p=1;p<=n;p++){
						for(int q=1;q<=m;q++){
							int index2=(p-1)*m+q;
							if(index2==index1) continue;
							if(abs(i-p)+abs(j-q)<=d) g.AddEdge(index1+n*m,index2,inf);
						}
					}
				}
			}
		}
		for(int i=1;i<=n;i++){
			scanf("%s",s+1);
			for(int j=1;j<=m;j++){
				if(s[j]=='L'){
					g.AddEdge(S,(i-1)*m+j,1);
					sum++;
				}
			}
		}
		int ans=sum-g.Maxflow(S,T);
		printf("Case #%d: ",Case++);
		if(ans==0) printf("no lizard was left behind.\n");
		else{
			if(ans==1) printf("1 lizard was left behind.\n");
			else printf("%d lizards were left behind.\n",ans);
		}
	}
	return 0;
}

思路

建图:
源点S编号0,网格的每个格子分成两个点i和i+n×m(n和m为网格的行和列数,其实i编号点是表示蜥蜴进来,而i+n×m编号的点是表示蜥蜴出去)
汇点t编号n×m×2+1.本题由于方便直接设为900
如果格子i上有蜥蜴,那么从s到i有边(s,i,1).
如果格子i能承受x次跳出,那么有边(i,i+n×m,x)
如果从格子i能直接跳出网格边界,那么有边(i+n×m,t,INF)
如果从格子i不能直接跳出网格,那么从i到离i距离<=d的网格j有边(i+n×m,j,INF). 注意这里的距离是abs(行号之差)+abs(列号之差)
最终我们求出的最大流就是能跳出网格的蜥蜴数.
注意输出的单复数即可

HDU 3338

题目要求

有一个填数字的游戏，需要你为白色的块内填一些值，在空白的上方和作方给出一些值，如果左下角有值说明下面列的和等于这个值，右上角的值等于这行后面的数的和
现在把空白的地方填上数字即可（只能填从1~9的数字，不限制一行是否有重复数字）

参考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
#include<bits/stdc++.h>
#define maxn 20500
#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;
}
void Reduce(){   
    for(int i=0;i<edges.size();i++) edges[i].cap-=edges[i].flow;
  }
}g;
char s[105][105][10];
bool vis[105][105];
char ans[105][105];
int main(){
//    freopen("input.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF){
        g.ClearAll(maxn);
        mm(vis,0);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                scanf("%s",s[i][j]+1);
                if(s[i][j][1]=='.'){
                    vis[i][j]=1;
                    g.AddEdge((i-1)*m+j,(i-1)*m+j+n*m,8);
                }
                else ans[i][j]='_';
            }
        }
        int S=0,T=n*m*2+1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(!vis[i][j]){
                    if(s[i][j][1]!='X'){
                        int temp=(s[i][j][1]-'0')*100+(s[i][j][2]-'0')*10+(s[i][j][3]-'0');
                        int num=(i-1)*m+j;
                        for(int k=i+1;k<=n && vis[k][j];k++){
                            temp--;
                            g.AddEdge(num,(k-1)*m+j,inf);
                        }
                        g.AddEdge(S,num,temp);
                    }
                    if(s[i][j][5]!='X'){
                        int temp=(s[i][j][5]-'0')*100+(s[i][j][6]-'0')*10+(s[i][j][7]-'0');
                        int num=(i-1)*m+j+n*m;
                        for(int k=j+1;k<=m && vis[i][k];k++){
                            temp--;
                            g.AddEdge((i-1)*m+k+n*m,num,inf);
                        }
                        g.AddEdge(num,T,temp);
                    }
                }
            }
        }
        g.Maxflow(S,T);
        g.Reduce();
        for(int i=0;i<g.edges.size();i++){
            if(g.edges[i].from<=n*m && g.edges[i].to>n*m){
                int x=g.edges[i].from/m+1;
                int y=g.edges[i].from%m;
                if(y==0){
                    y=m;
                    x--;
                }
                ans[x][y]=8-g.edges[i].cap+1+'0';
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                printf("%c",ans[i][j]);
                if(j==m) printf("\n");
                else printf(" ");
            }
        }
    }
    return 0;
}

思路

这题可以用网络流做。以空白格为节点，假设流是从左流入，从上流出的，流入的容量为行和，流出来容量为列和，其余容量不变。求满足的最大流。
由于流量有上下限限制，可以给每个数都减掉1，则填出来的数字范围为0—8, 就可以用单纯的网络流搞定了。求出来再加上就可以了。
建图：
一共有四类点：
1.构造源点S，汇点T
2.有行和的格子，此类节点设为A
3.空白格，设为B
4.有列和的格子，设为C
则可以建边：
1.(S, A) 容量和行和
2.(A, B) 容量为8
3.(B, C) 容量为8
4.(C, T) 容量为列和

本文标题:网络流拓展四

文章作者:Hippopmonkey

发布时间:2017-09-19, 17:27:56

最后更新:2017-09-25, 17:43:07

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

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

文章目录
  1. 1. 网络流拓展四
    1. 1.1. HDU 3081
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码(并查集)
      3. 1.1.3. 参考AC代码(floyd传递闭包)
      4. 1.1.4. 思路
    2. 1.2. HDU 3416
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. HDU 3277
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. uva 10480
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. HDU 2732
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. HDU 3338
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路
|