网络流拓展六

自用笔记算法

网络流拓展六

uva 1660

题目要求

紫书P380
最少删除多少个点 破坏原图的连通性

参考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 150
#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;
};
vector<Edge>ori;
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);
		for(int i=0;i<n;i++){
			if(i==0) g.AddEdge(0,n,inf);
			g.AddEdge(i,i+n,1);
		}
		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=inf;
		ori=g.edges;
		for(int t=1;t<n;t++){
			g.edges=ori;
			for(int i=0;i<g.edges.size();i++){
				if(g.edges[i].from==t && g.edges[i].to==t+n){
					g.edges[i].cap=inf;
					break;
				}
			}
			ans=min(ans,g.Maxflow(0,t+n));
		}
		if(ans==inf) ans=n;
		printf("%d\n",ans);
	}
	return 0;
}

思路

经典的最小割问题 不过不是割边而是割点
为了形成割，那么必须让点具有“流量”的性质 我们将每个点拆成两个点 连一条容量为1的边 那么每个点就被赋予了流量的性质 边的容量为无穷大 因为要删除点而不是边
另外因为我们不知道要割哪两个集合才能使得最大流最小 所以我们可以枚举源点和汇点
我们固定源点为0，只需要枚举汇点即可 取得的最小的最大流就是使得图不连通的最小割
注意：
1.不要忘了令源点和汇点的容量为无穷大 因为我们是不删除这两个点的 对应着0到n的容量为inf 以及每次对应的t到t+n为inf
2.需要设置一个ori保存最原始的edges 对应每个t 要在ori的基础上修改inf
3.若ans==inf表示0与所有点都无法形成最小割 那么只能删除所有的点

uva 12433

题目要求

紫书P384

参考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
#include<bits/stdc++.h>
#define maxn 300
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int t,N,C,R;
int r[maxn],c[maxn],p[maxn],d[maxn],s[maxn];
int Case=1;
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 temp){
		int flow=0,cost=0;
		while(BellmanFord(s,t,flow,cost));
		printf("Case %d: ",Case++);
		if(flow==temp) printf("%d\n",cost);
		else puts("impossible");
	}
}mc;
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&N,&C,&R);
		int f=0;
		for(int i=1;i<=N;i++) scanf("%d",&r[i]),f+=r[i];
		for(int i=1;i<=C;i++) scanf("%d%d",&c[i],&p[i]);
		for(int i=1;i<=R;i++) scanf("%d%d",&d[i],&s[i]);
		mc.init(maxn);
		int S=0,T1=2*N+1,T2=2*N+2;
		for(int i=1;i<=N;i++){
			mc.AddEdge(S,i,r[i],0);
			mc.AddEdge(i+N,T2,r[i],0);
			mc.AddEdge(T1,i+N,inf,0);
		}
		for(int i=1;i<=C;i++) mc.AddEdge(S,T1,c[i],p[i]);
		for(int i=1;i<N;i++) mc.AddEdge(i,i+1,inf,0);
		for(int i=1;i<=N;i++){
			for(int j=1;j<=R;j++){
				if(i+d[j]+1<=N) mc.AddEdge(i,i+d[j]+1+N,inf,s[j]);
			}
		}
		mc.Mincost(S,T2,f);
	}
	return 0;
}

思路

很神奇的建图：
假设有5天的租车需求，虚拟出2×n+2即12个节点 0为源点 12为汇点
源点到12345流量为r[i],费用为0
678910到汇点流量为r[i-n]，费用为0
虚拟第2×n+1个节点为买车途径 源点到2×n+1节点花费为p[i],流量为c[i] 存在重边 对于每一个i+n节点 其来源有两个 一个是2×n+1节点 即购买新车 一个是之前的车辆送去维修后的可用车辆。
连接i和i+1节点，流量为INF，花费为0。同时根据维修的天数
连接i和d[j]+i+1+n节点，花费为s[i]，流量为INF。
若满流输出cost 否则输出impossible

HDU 5520

题目要求

NxM的格子有些上面有数字，现在要把奇数跟偶数配对连起来，其他的格子连成一个个回路，单独的相邻两个格子相连也算是一个回路按两条边算，连线不能相交，相邻两个格子相连的费用全都给出来了，求最少的费用。

参考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
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
#define maxn 5050
using namespace std;
int n,m;
int Case=1;
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("Case #%d: %d\n",Case++,cost);
		else printf("Case #%d: %d\n",Case++,-1);
	}
}mc;
int mp[55][55],mark[55][55];
int cnt;
int main(){
//	freopen("input.txt","r",stdin);
	int t;
	scanf("%d",&t);
	while(t--){
		mc.init(maxn);
		scanf("%d%d",&n,&m);
		int S=0,T=5005;
		cnt=0;
		mm(mark,0);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				scanf("%d",&mp[i][j]);
				mark[i][j]=++cnt;
			}
		}	
		int num=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(mp[i][j]==0){
					mc.AddEdge(S,mark[i][j],1,0);
					mc.AddEdge(mark[i][j]+n*m,T,1,0);
					num++;
				}
				else if(mp[i][j]&1){
					mc.AddEdge(S,mark[i][j],1,0);
					num++;
				}
				else mc.AddEdge(mark[i][j]+n*m,T,1,0);
			}
		}
		for(int i=1;i<n;i++){
			for(int j=1;j<=m;j++){
				int x;
				scanf("%d",&x);
				mc.AddEdge(mark[i][j],mark[i+1][j]+n*m,1,x);
				mc.AddEdge(mark[i+1][j],mark[i][j]+n*m,1,x);
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<m;j++){
				int x;
				scanf("%d",&x);
				mc.AddEdge(mark[i][j],mark[i][j+1]+n*m,1,x);
				mc.AddEdge(mark[i][j+1],mark[i][j]+n*m,1,x);
			}
		}
		mc.Mincost(S,T,num);
	}
	return 0;
}

思路

最小费用流水题
0点和奇数点向S连一条边 flow=1 cost=0 确保只能走一次
0点和偶数点向T连一条边 flow=1 cost=0
对于每个向左和向下的相邻格子连一条边 flow=1 cost=x
跑一边mcmf 如果满流输出cost 否则输出-1

cf 884f

题目要求

给定一个字符串s 长度为偶数 每个位置有一个权值bi
现定义一个字符串是anti回文串 满足ai不等于a(m-i+1)
求用给定的字符串s能构成的anti回文串 使得ti==si位置的点权和最大是多少

参考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 105
#define mm(a,b) memset(a,b,sizeof(a)) 
#define inf 0x3f3f3f3f
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;
	}
	int Mincost(int s,int t){
		int flow=0,cost=0;
		while(BellmanFord(s,t,flow,cost));
		return cost;
	}
}g;
char s[maxn];
int a[maxn],hashh[30];
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d",&n)!=EOF){
		scanf("%s",s+1);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		mm(hashh,0);
		for(int i=1;i<=n;i++) hashh[s[i]-'a'+1]++;
		int S=0,T=100;
		g.init(maxn);
		for(int i=1;i<=26;i++) g.AddEdge(S,i,hashh[i],0);
		for(int i=1;i<=n/2;i++) g.AddEdge(i+26,T,2,0);
		for(int i=1;i<=26;i++){
			char c='a'+(i-1);
			for(int j=1;j<=n/2;j++){
				if(s[j]==c && s[n-j+1]==c) g.AddEdge(i,j+26,1,-max(a[j],a[n-j+1]));
				else if(s[j]!=c && s[n-j+1]!=c) g.AddEdge(i,j+26,1,0);
				else if(s[j]==c && s[n-j+1]!=c) g.AddEdge(i,j+26,1,-a[j]);
				else if(s[j]!=c && s[n-j+1]==c) g.AddEdge(i,j+26,1,-a[n-j+1]);
			}
		}
		int ans=-g.Mincost(S,T);
		printf("%d\n",ans);
	}
	
	return 0;
}

思路

最小费用最大流 比较难建图 类似与匹配的思想
本题相当于把每对头尾2个数字绑在一起当作一个点做匹配
统计每个字母出现的次数hashh 每个字母向S连一条容量为hashh 费用为0的边
再加上n/2个点 每个点表示头尾绑在一起的2个点 每一对点向T连一条流量为2 费用为0的边
考虑中间的建图：遍历每一个字母c 如果si和s(m-i+1)两个点都是c 那么该字母向该对数字连一条流量为1 费用为-max(ai,a(m-i+1))的边
如果两个点均不是c 费用0 如果有一个点i是c 那么费用为-a[i] 跑一边mcmf -ans就是所求
这是因为 每一个字母相当于在一个pair中找匹配 如果2个都匹配 取一个最大的 如果2个都不匹配 不匹配 如果只有一个匹配 费用为那个匹配的权值
三块流量分别为hashh 1 2 满足每个字母只能匹配可以匹配的一个位置

2016icpc北京区域赛C

题目要求

有一个N×N的01矩阵 0代表白色 1代表黑色
给出N×N/2个点对 点对之间的2个点可以互相交换
每行和每列有一个黑色点的上下界限制
问最少经过多少次交换后可以满足行和列的限制 若不能输出-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
#include<bits/stdc++.h>
#define N 55
#define maxn 110   //最大顶点数
#define inf 0x3f3f3f3f
using namespace std;
int n;
int s,t,sups,supt;
int chs[N][N],rl[N],rh[N],cl[N],ch[N],r[N],c[N],h[maxn];
typedef pair<int,int> P;   //first保存最短距离，second保存顶点编号
struct Edge{
	int to,cap,rev, cost;
}e;
struct MCMF_{
	vector<Edge>g[maxn];   //图的邻接表表示
	int dist[maxn];   //顶点的势、最短距离，若cost为整数，改INT
	int prevv[maxn],preve[maxn],V;    //最短路中的前驱节点、对应的边、顶点数
	int digflow;
	void init(int n){
		for(int i=0;i<=supt;i++) g[i].clear();
		this->V=n;
		digflow=0;
	}
	void addedge(int from,int to,int cap,int cost){ 
	    e.to=to,e.cap=cap,e.rev=g[to].size(),e.cost=cost;
	    g[from].push_back(e);
	    e.to=from,e.cap=0,e.rev=g[from].size()-1,e.cost=-cost;
	    g[to].push_back(e);
	}
	void addedge(int from,int to,int low,int up,int cost){
	    digflow+=low;
	    addedge(sups,to,low,cost);
	    addedge(from,supt,low,cost);
	    addedge(from,to,up-low,cost);
	}
	int mincostflow(int s,int t){    //求解从s到t,流量为f的最小费用流
	    int res=0;
	    int f=digflow;
	    memset(h,0,sizeof(4*t+4));
	    while(f>0){
	        priority_queue<P,vector<P>,greater<P> >que;
	        fill(dist,dist+V,inf);
	        dist[s]=0;
	        que.push(P(0,s));
	        while(!que.empty()){
	            P p=que.top(); que.pop();
	            int v=p.second;
	            if(dist[v]<p.first) continue;
	            for(int i=0;i<g[v].size();i++) {
	                Edge &E=g[v][i];
	                if(E.cap>0 && dist[E.to]>dist[v]+E.cost+h[v]-h[E.to]){
	                    dist[E.to]=dist[v]+E.cost+h[v]-h[E.to];
	                    prevv[E.to]=v;
	                    preve[E.to]=i;
	                    que.push(P(dist[E.to],E.to));
	                }
	            }
	        }
	        if(dist[t]==inf) return -1;
	        for(int v=0;v<V;v++) h[v]+=dist[v];  
	        int d=f;   //沿s到t的最短路尽量增广
	        for(int v=t;v!=s;v=prevv[v]) d=min(d,g[prevv[v]][preve[v]].cap);
	        f-=d;
	        res+=h[t]*d;
	        for(int v=t;v!=s;v=prevv[v]){
	            Edge &E=g[prevv[v]][preve[v]];
	            E.cap-=d;
	            g[v][E.rev].cap+=d;
	        }
	    }
	    return res;
	}
}g;
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d",&n)!=EOF){
        s=2*n+1,sups=0;
        t=2*n+2,supt=2*n+3;
        memset(c,0,sizeof(c));
        memset(h,0,sizeof(h));
        int mx=0;
        g.init(supt+1);
        for(int i=1;i<=n;i++){
        	for(int j=1;j<=n;j++){
	            scanf("%d",&chs[i][j]);
	            c[j]+=chs[i][j];
	            h[i]+=chs[i][j];
	            mx+=chs[i][j];
        	}   
		}
        for(int i=1;i<=n;i++){
            g.addedge(s,i,h[i],h[i],0);
            g.addedge(s,i+n,c[i],c[i],0);
        }
        for(int i=1;i<=n;i++){
            scanf("%d%d",&rl[i],&rh[i]);
            g.addedge(i,t,rl[i],rh[i],0);
        }
        for(int i=1;i<=n;i++){
            scanf("%d%d",&cl[i],&ch[i]);
            g.addedge(i+n,t,cl[i],ch[i],0);
        }
        for(int i=1;i<=n*n/2;i++){
            int x1,y1,x2,y2;
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            if(chs[x1][y1]==chs[x2][y2]) continue;
            if(chs[x1][y1]==0) swap(x1,x2),swap(y1,y2);
            if(x1==x2) g.addedge(n+y1,n+y2,1,1);  
			else g.addedge(x1,x2,1,1);
        }
        g.addedge(t,s,mx,inf,0);
        int ans=g.mincostflow(sups,supt);
        printf("%d\n",ans);
    }
}

思路

有源有汇有上下界最小费用最大流
参考博客
实际上就是求s到t 最少黑点的移动个数可以满足流量的限制
有源有汇转成无源无汇 由t再连向s 下界为黑色点的个数 上界为inf 构成循环流 构成无源无汇
用模版建图

2017icpc青岛区域赛K

转跳链接
拆分成三段的mcmf

gym(2017-united-kingdom-ireland-programming-contest-ukiepc)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
#include<bits/stdc++.h>
#define maxn 1050
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
int b[maxn]; 
struct node{
	int x,y;
}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;
vector<int>ans[maxn];
void dfs(int len,int x){
	if(x==0) return;
	x-=n;
	ans[len].push_back(x);
	for(int i=0;i<g.G[x].size();i++){
		if(g.edges[g.G[x][i]].flow<0){
			dfs(len,g.edges[g.G[x][i]].to);
			break;
		}
	}
}
int main(){
//	freopen("input.txt","r",stdin);
	int S=0,T=500,T2=1000;
	g.ClearAll(maxn);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
	scanf("%d",&m);
	for(int i=1;i<=m;i++) scanf("%d",&b[i]);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(a[j].y>=b[i]) g.AddEdge(j+n,T+i,1);
		}
	}
	for(int i=1;i<=m;i++) g.AddEdge(T+i,T2,1);
	for(int i=1;i<=n;i++){
		if(a[i].x==0) g.AddEdge(S,i,1);
		g.AddEdge(i,i+n,1);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) continue;
			if(a[i].y>=a[j].x) g.AddEdge(i+n,j,1);
		}
	}
	int re=g.Maxflow(S,T2);
	if(re!=m) puts("impossible");
	else{
		for(int i=1;i<=m;i++){
			for(int j=0;j<g.G[T+i].size();j++){
				if(g.edges[g.G[T+i][j]].flow<0){
					dfs(i,g.edges[g.G[T+i][j]].to);
				}
			}
		}
		for(int i=1;i<=m;i++){
			for(int j=ans[i].size()-1;j>=0;j--){
				if(j==0) printf("%d\n",ans[i][j]);
				else printf("%d ",ans[i][j]);
			}
		}
	}
	return 0;
}

思路

建图很简单 注意两个大于等于即可
关键在于输出路径 反向边flow小于0表示有流量经过
类似与背包dp的输出路径 递归逆序输出即可

la 7264

题目要求

n个点 m条边 目标点S 每条边有一个权值
边权表示删除这条边的花费
如果要取到点S 必须要取到点S的前驱结点
第一行n个值表示正常取前驱每个点的点权
下一行的n个值表示不考虑前驱直接取到某个点的点权
问取到S点的最少花费

参考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 inf 0x3f3f3f3f
#define maxn 1050
using namespace std;
int t,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;
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&n,&m,&k);
		g.ClearAll(maxn);
		int S=0,T=2*n+1;
		while(m--){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			g.AddEdge(u+n,v,w);
		}
		for(int i=1;i<=n;i++){
			int x;
			scanf("%d",&x);
			g.AddEdge(S,i,x);
		}
		for(int i=1;i<=n;i++){
			int x;
			scanf("%d",&x);
			g.AddEdge(i,i+n,x);
		}
		g.AddEdge(k+n,T,inf);
		int ans=g.maxflow(S,T);
		printf("%d\n",ans);
	}
	return 0;
}

思路

可以转换成最小割模型
s到i为原始点权 i到i+n为直接取到的点权 u+n到v为边权 k+n连到T
割断S到T(实际为k)的连通性的最小割就是所求

本文标题:网络流拓展六

文章作者:Hippopmonkey

发布时间:2017-10-09, 16:20:39

最后更新:2017-11-16, 21:56:16

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

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

文章目录
  1. 1. 网络流拓展六
    1. 1.1. uva 1660
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. uva 12433
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. HDU 5520
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. cf 884f
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. 2016icpc北京区域赛C
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. 2017icpc青岛区域赛K
    7. 1.7. gym(2017-united-kingdom-ireland-programming-contest-ukiepc)K
      1. 1.7.1. 题目要求
      2. 1.7.2. 参考AC代码
      3. 1.7.3. 思路
    8. 1.8. la 7264
      1. 1.8.1. 题目要求
      2. 1.8.2. 参考AC代码
      3. 1.8.3. 思路
|