网络流拓展五

自用笔记算法

网络流拓展五

uva 11082

题目要求

紫书P374

参考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
#include<bits/stdc++.h>
#define maxn 50
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int t,n,m;
int a[maxn],b[maxn];
int c[maxn],d[maxn];
int Case=1;
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;
}
void 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);
    }
}
}g;
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		g.ClearAll(maxn);
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=m;i++) scanf("%d",&b[i]);
		for(int i=1;i<=n;i++) c[i]=a[i]-a[i-1],c[i]-=m;
		for(int i=1;i<=m;i++) d[i]=b[i]-b[i-1],d[i]-=n;
		int S=0,T=n+m+1;
		for(int i=1;i<=n;i++) g.AddEdge(S,i,c[i]);
		for(int i=1;i<=m;i++) g.AddEdge(n+i,T,d[i]);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				g.AddEdge(i,n+j,19);
			}
		}
		g.Maxflow(S,T);
		printf("Matrix %d\n",Case++);
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<g.G[i].size();j++){
    			if(j==g.G[i].size()-1) printf("%d\n",g.edges[g.G[i][j]].flow+1);
    			else printf("%d ",g.edges[g.G[i][j]].flow+1);
			}
		}
		puts("");
	}
	return 0;
}

思路

紫书P374
注意：
1.要把ab数组转换cd数组 建图里的点是每一行或每一列的和而非前缀和
2.注意输出矩阵的时候 j要从1开始 因为edges[i][0]里已经存了S到i的反向边了 该点要跳过
3.本题转换成网络流要把1-20转换成0-19 答案在+1

uva 1658

题目要求

紫书P375

参考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
#include<bits/stdc++.h>
#define maxn 2500
#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,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 main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d",&n,&m)!=EOF){
		mc.init(maxn);
		int S=0,T=2*n+1;
		mc.AddEdge(S,1,2,0);
		mc.AddEdge(T-1,T,2,0);
		mc.AddEdge(1,1+n,inf,0);
		mc.AddEdge(n,n+n,inf,0);
		for(int i=2;i<=n-1;i++) mc.AddEdge(i,i+n,1,0);
		for(int i=1;i<=m;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			mc.AddEdge(u+n,v,1,w);
		}		
		int ans=mc.Mincost(S,T);
		printf("%d\n",ans);
	}
	return 0;
}

思路

紫书P375
注意：
1.问题等价于每个点只能经过一次且流量为2的mcmf 拆点
2.注意1到1+n和n到n+n要建一条流量为2或者inf的边 或者也可以设1+n为S n为T来避免这2条语句

uva 12264

题目要求

给n个点的无权无向图（n<=100），每个点有一个非负数ai。若ai==0则此点归敌方所有，若ai>0则此点归你且上面有ai个属于你的士兵。
保证至少有一个属于你的点与敌方的点相邻。你可以让你的每个士兵最多移动一次，每次可以待在原地或者去到相邻的属于你的领地，但每个点至少要留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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<bits/stdc++.h>
#define maxn 350
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int t,n;
int a[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;
char ss[maxn][maxn];
bool ok[maxn];
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=n;i++) scanf("%s",ss[i]+1);
		int l=0,r=10000,ans=0;
		while(l<=r){
			int mid=l+r>>1;
			int S=0,T=2*n+1;
			g.ClearAll(maxn);
			int f1=0,f2=0;
			mm(ok,false);
			for(int i=1;i<=n;i++){
				if(!a[i]) continue;
				g.AddEdge(S,i,a[i]);
				g.AddEdge(i,i+n,a[i]);
				for(int j=1;j<=n;j++){
					if(ss[i][j]=='Y'){
						if(!a[j]) ok[i]=true;
						else g.AddEdge(i,j+n,inf);	
					}
				}
			}
			for(int i=1;i<=n;i++){
				if(ok[i]){
					g.AddEdge(i+n,T,mid);
					f1+=mid;
				}
				else if(a[i]){
					g.AddEdge(i+n,T,1);
					f1++;
				}
			}
			f2=g.Maxflow(S,T);
			if(f1==f2){
				ans=mid;
				l=mid+1;
			}
			else r=mid-1;
		}
		printf("%d\n",ans);
	}
	return 0;
}

思路

二分网络流
因为每个士兵只能移动一次 所以拆点 i到i+n连边 容量为a[i] 表示可以不移动
每个士兵人数大于0的点向S连一条边 容量为a[i]
对于每个士兵人数大于0的点 再遍历到达的终点 如果b[i]为0 记录下i的位置 表示该点是和敌兵相邻的点 否则i到j+n连一条容量为inf的边 表示士兵到相邻点的移动
再for一遍1到n 如果该点和敌兵相连 连一条容量为mid的流量到T 否则连一条容量为1的边到T 表示该点最少得有一个士兵(a[i]==0的点依旧跳过)
二分最大流即可
最小值最大：与敌兵相连的人尽可能平均 所以容量均设为mid 最大满流值下的mid

uva 1349

题目要求

紫书P375

参考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
#include<bits/stdc++.h>
#define maxn 300
#define inf 0x3f3f3f3f 
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n;
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 num){
		int flow=0,cost=0;
		while(BellmanFord(s,t,flow,cost));
		if(flow==num) printf("%d\n",cost);
		else printf("N\n");
	}
}mc;
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d",&n)!=EOF){
		if(n==0) break;
		mc.init(maxn);
		int S=0,T=2*n+1;
		int to,w;
		for(int i=1;i<=n;i++){
			while(scanf("%d",&to)){
				if(to==0) break;
				scanf("%d",&w);
				mc.AddEdge(i,to+n,1,w);
			}
		}
		for(int i=1;i<=n;i++){
			mc.AddEdge(S,i,1,0);
			mc.AddEdge(i+n,T,1,0);
		}
		mc.Mincost(S,T,n);
	}
	return 0;
}

思路

紫书P375
每个点恰好属于一个有向圈==每个点只有唯一一个后继==完美匹配
网络流建图匹配
如果flow==n 说明满流 输出min_cost 否则输出N

uva 1515

题目要求

紫书P376

参考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
#include<bits/stdc++.h>
#define maxn 3000
#define inf 0x3f3f3f3f 
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int t,n,m;
int d,f,b;
int dirx[4]={0,0,1,-1};
int diry[4]={1,-1,0,0};
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 mp[55][55];
int mark[55][55];
int cnt;
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		g.ClearAll(maxn);
		scanf("%d%d",&m,&n);
		scanf("%d%d%d",&d,&f,&b);
		for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
		mm(mark,0),cnt=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++) mark[i][j]=++cnt;
		}
		int ans=0;
		for(int i=1;i<=n;i++){
			if(mp[i][1]=='.') mp[i][1]='#',ans+=f;
			if(mp[i][m]=='.') mp[i][m]='#',ans+=f; 
		}
		for(int i=1;i<=m;i++){
			if(mp[1][i]=='.') mp[1][i]='#',ans+=f;
			if(mp[n][i]=='.') mp[n][i]='#',ans+=f;
		}
		int S=0,T=n*m+1;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(i==1 || i==n || j==1 || j==m) g.AddEdge(S,mark[i][j],inf);
				else if(mp[i][j]=='#') g.AddEdge(S,mark[i][j],d);
				else if(mp[i][j]=='.') g.AddEdge(mark[i][j],T,f);
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				for(int k=0;k<4;k++){
					int nextx=i+dirx[k];
					int nexty=j+diry[k];
					if(nextx<1 || nextx>n || nexty<1 || nexty>m) continue;
					g.AddEdge(mark[i][j],mark[nextx][nexty],b);
				}
				
			}
		}
		ans+=g.Maxflow(S,T);
		printf("%d\n",ans);
	}
	return 0;
}

思路

紫书P376
其实就是求最小割
首先把四周的.均换成# 计算出代价
所有的草地向S连边 若是四周的点 容量为inf 否则容量为d 所有洞和T相连 容量为d
代表把一块草地变成洞和洞变成草地的代价 接着矩阵的所有相邻边相连 容量为b
跑一边最大流 等值的最小割就是所求
最小割就是切断S和T的最小割 这里就是切断所有草地和洞的联系 只要满足切断的所有边使得草地无法到达洞 即为满足题意

uva 10735

题目要求

紫书P376-377
输出混合图的欧拉回路

参考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
149
#include<bits/stdc++.h>
#define maxn 300
#define maxm 520 
#define inf 0x3f3f3f3f 
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int t,n,m;
int in[maxn],out[maxn];
int vis[maxm];
struct Edge{
  int from, to, cap, flow;
};
vector<Edge>ori_edges;
vector<int>re;
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;
void find_path(int u,vector<int>&path){
	for(int i=0;i<g.G[u].size();i++){
		int x=g.G[u][i];
		if(vis[x]) continue;
		vis[x]=1;
		Edge& e=ori_edges[x];
		find_path(e.to,path);
		path.push_back(e.to);
	}
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		g.ClearAll(maxn);
		ori_edges.clear(),re.clear();
		mm(in,0),mm(out,0),mm(vis,0);
		for(int i=1;i<=m;i++){
			int u,v;
			char op;
			scanf("%d %d %c",&u,&v,&op);
			if(op=='U') g.AddEdge(u,v,1);
			else ori_edges.push_back((Edge){u,v,0,0});
			out[u]++,in[v]++;
		}
		int flag=0;
		for(int i=1;i<=n;i++){
			if((in[i]-out[i])%2){
				flag=1;
				break;
			}
		}
		if(flag){
			puts("No euler circuit exist");
			if(t) puts("");
			continue;
		}
		int S=0,T=n+1;
		int sum=0;
		for(int i=1;i<=n;i++){
			if(out[i]>in[i]) g.AddEdge(S,i,(out[i]-in[i])/2),sum+=(out[i]-in[i])/2;
			else if(in[i]>out[i]) g.AddEdge(i,T,(in[i]-out[i])/2); 
		}
		int ans=g.Maxflow(S,T);
		if(ans<sum){
			puts("No euler circuit exist");
			if(t) puts("");
			continue;
		}
		for(int i=1;i<=n;i++){
			for(int j=0;j<g.G[i].size();j++){
				Edge& e=g.edges[g.G[i][j]];
				if(e.cap==0) continue;
				if(e.from<1 || e.from>n) continue;
				if(e.to<1 || e.to>n) continue;
				if(e.flow>=1) ori_edges.push_back((Edge){e.to,e.from,0,0});
				else ori_edges.push_back((Edge){e.from,e.to,0,0});
			}
		}
		g.ClearAll(maxn);
		for(int i=0;i<ori_edges.size();i++){
			int x=ori_edges[i].from;
			g.G[x].push_back(i);
		}
		find_path(1,re);
		printf("1");
		for(int i=re.size()-1;i>=0;i--) printf(" %d",re[i]);
		puts("");
		if(t) puts("");
	}
	return 0;
}

思路

紫书P377
有向边先存入ori 对无向边固定任意方向建图 若满流说明网络流能把那些多余的出度运送到T
对于有流量的边等价于这条变需要反向 那么反向存入ori
接着更新G数组让他对应ori 一遍dfs记录下路径 反向输出即可
注意：
1.vis是以edges里存的边的位置来判断有没有出现过 所以至少开500
2.注意输出格式 样例与样例之间有空行 提前输出不存在的时候也需要判断是否输出空行

uva 1659 && HDU 2982

题目要求

紫书P378

参考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
#include<bits/stdc++.h>
#define maxn 200
#define inf 0x3f3f3f3f 
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
const double eps=1e-8;
int n,x,y;
struct Edge{
    int from,to,cap;
    double flow,cost;
    Edge(int u,int v,int c,double f,double w):from(u),to(v),cap(c),flow(f),cost(w){}
};
struct node{
	int x,y;
	vector<int>e;
}a[maxn];
struct MCMF{
    int n,m;  
    vector<Edge>edges;
    vector<int>G[maxn];
    int inq[maxn];
    double d[maxn];
    int p[maxn];
    double 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,double cap,double 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,double& flow,double& cost){
        int cnt[maxn];
        int k=-1;
        memset(cnt,0,sizeof(cnt));
        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(unsigned 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>eps){
                    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(++cnt[e.to]>n){k=u;goto here;}}
                }
            }
        }
        here:
        if(k==-1) return false;
        int vis[maxn];
        memset(vis,0,sizeof(vis));
        for(int u=k;;u=edges[p[u]].from){
            vis[u]++;
            if(vis[u]==2) {k=u;break;}
        }
        flow+=a[k];
        edges[p[k]].flow+=a[k];
        edges[p[k]^1].flow-=a[k];
        cost+=edges[p[k]].cost;  
        for(int u=edges[p[k]].from;u!=k;u=edges[p[u]].from){
            edges[p[u]].flow+=a[k];
            edges[p[u]^1].flow-=a[k];
            cost+=edges[p[u]].cost;
        }
        return true;
    } 
    double MincostMaxflow(int s){
        double flow=0,cost=0;
        while(BellmanFord(s,flow,cost));
        return cost;
    }
}g;
double dist(int x1,int x2){
	double dis1=a[x1].x-a[x2].x;  
    double dis2=a[x1].y-a[x2].y;  
    return sqrt(dis1*dis1+dis2*dis2);  
}
int Case=1;
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d",&n)!=EOF){
		if(n==0) break;
		scanf("%d%d",&x,&y);
		int S=0;
		g.init(maxn);
		for(int i=1;i<=n;i++){
			scanf("%d%d",&a[i].x,&a[i].y);
			a[i].e.clear();
			int x;
			while(scanf("%d",&x)){
				if(x==0) break;
				a[i].e.push_back(x);
			}
		}
		for(int i=1;i<=n;i++){
			g.AddEdge(S,i,1,0);
			for(int j=0;j<a[i].e.size();j++){
				g.AddEdge(i,a[i].e[j],1,-dist(i,a[i].e[j])*x+y);
			}
		}
		double ans=g.MincostMaxflow(S);
		printf("Case %d: %.2lf\n",Case++,-ans+eps);
	}
	return 0;
}

参考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 200
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
const double eps=1e-8;
int n,x,y;
int du[maxn];
struct Edge{
	int from,to,cap,flow;
	double cost;
	Edge(int from,int to,int cap,int flow,double cost):from(from),to(to),cap(cap),flow(flow),cost(cost){}
};
struct node{
	int x,y;
	vector<int>e;
}a[maxn];
struct MCMF{
	int n,m,s,t;
	vector<Edge>edges;
	vector<int>G[maxn];
	int inq[maxn],p[maxn],a[maxn];
	double d[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,double 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,double& 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>eps){
					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;
	}
	double Mincost(int s,int t){
		int flow=0;
		double cost=0;
		while(BellmanFord(s,t,flow,cost));
		return cost;
	}
}mc;
double dist(int x1,int x2){
	double dis1=a[x1].x-a[x2].x;  
    double dis2=a[x1].y-a[x2].y;  
    return sqrt(dis1*dis1+dis2*dis2);  
}
int Case=1;
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d",&n)!=EOF){
		if(n==0) break;
		scanf("%d%d",&x,&y);
		int S=0,T=n+1;
		mm(du,0);
		mc.init(maxn);
		for(int i=1;i<=n;i++){
			scanf("%d%d",&a[i].x,&a[i].y);
			a[i].e.clear();
			int x;
			while(scanf("%d",&x)){
				if(x==0) break;
				a[i].e.push_back(x);
			}
		}
		double sum=0;
		for(int i=1;i<=n;i++){
			for(int j=0;j<a[i].e.size();j++){
				int next=a[i].e[j];
				double w=-dist(i,next)*x+y;
				if(w<0){
					mc.AddEdge(next,i,1,-w);
					sum+=w;
					du[i]--,du[next]++;
				}
				else mc.AddEdge(i,next,1,w);
			}
		}
		for(int i=1;i<=n;i++){
			if(du[i]>0) mc.AddEdge(S,i,du[i],0);
			else if(du[i]<0) mc.AddEdge(i,T,-du[i],0);
		}
		double ans=mc.Mincost(S,T);
		printf("Case %d: %.2lf\n",Case++,-(ans+sum)+eps);
	}
	return 0;
}

思路

紫书P378
注意精度问题
思路1
只设一个源点S连向所有的点 容量为1费用为0 无汇点 正常按照边权取反建图
跑一边寻找负费用增广圈的mcmf即可
但方法一非常耗时
思路2
1.先将所有边权取反。
2.建边。正权值的边容量为1，费用为权值。负权值的边u->v拆成3条边，分别是S->v，v->u，u->T，容量都为1，v->u费用为负权的相反数，其他2条费用为0。
这样会出现某个点有多条边连到S或T，可以互相抵消到一方为0为止，统计剩下多少条k，将其中1条的容量设为k，其他的全部删掉。如果全部抵消掉了，那就将连S和T的边全部删掉。(这个删边的方法有技巧)
3.跑一次最小费用流得到的总费用，加上所有负权之和之后（注：此时答案已为负的），再取反即得到最大费用。
删边技巧是，在建这S->v，v->u，u->T 三条边时，先建中间那条，统计该点连到S几次，减去连到T点几次，结果若为正，则与S连一条边，容量就是几次，若负，同理。

本文标题:网络流拓展五

文章作者:Hippopmonkey

发布时间:2017-10-04, 17:26:50

最后更新:2017-10-10, 15:07:39

原始链接:http://xuboming8.github.io/2017/10/04/网络流拓展五/

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

文章目录
  1. 1. 网络流拓展五
    1. 1.1. uva 11082
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. uva 1658
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. uva 12264
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. uva 1349
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. uva 1515
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. uva 10735
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路
    7. 1.7. uva 1659 && HDU 2982
      1. 1.7.1. 题目要求
      2. 1.7.2. 参考AC代码(寻找负费用增广圈)
      3. 1.7.3. 参考AC代码(处理负权+重边)
      4. 1.7.4. 思路
|