网络流拓展一

自用笔记算法

二分图多重匹配

与普通二分图匹配的区别在于一个点可匹配多个点
普通二分图匹配一般求最大(完美)带权匹配值
二分图多重匹配一般求是否有合理的分配使得形成多重匹配

HDU 3605

题目要求

一个人可以去多个星球 输出每个人可以去的星球的情况 数组g中存储1代表可以去 0代表不能去
一个星球最多可以容纳某个数量的人 问是否可以有某种分配方式使得满足多重匹配

参考AC代码(多重匹配hungary模版)

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
#include<bits/stdc++.h>
#define maxn 100050
#define maxm 15
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
int n,m,w[maxm],cnt[maxm];  
int g[maxn][maxm],match[maxm][maxn];  
bool vis[maxm];  
bool dfs(int x){ 
    for(int i=0;i<m;i++)  
        if(!vis[i]&&g[x][i]){
            vis[i]=1;  
            if(cnt[i]<w[i]){
                match[i][cnt[i]++]=x;  
                return true;  
            }  
            for(int j=0;j<cnt[i];j++)  
                if(dfs(match[i][j])){
                    match[i][j]=x;  
                    return true;  
                }  
        }  
    return false;  
}  
bool ok(){    
    mm(cnt,0);
    for(int i=0;i<n;i++){
        mm(vis,0);
        if(!dfs(i)) return false;  
    }  
    return true;  
}  
int main(){
//    freopen("input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    while(cin>>n>>m){ 
        for(int i=0;i<n;i++)  
            for(int j=0;j<m;j++)  
                cin>>g[i][j];  
        for(int i=0;i<m;i++) cin>>w[i];  
        puts(ok()?"YES":"NO");  
    }  
}

参考AC代码(dinic)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 1500
#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 dp[maxn];
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d",&n,&m)!=EOF){
		g.ClearAll(maxn);
		mm(dp,0);
		int S=0,T=m+(1<<m)+1;
		for(int i=0;i<n;i++){
			int sum=0;
			for(int j=0;j<m;j++){
				int x;
				scanf("%d",&x);
				if(x) sum+=(1<<j);	
			}
			dp[sum]++;
		}
		for(int i=1;i<(1<<m);i++){
			if(dp[i]) g.AddEdge(S,i,dp[i]);
			for(int j=0;j<m;j++){
				if(i & (1<<j)) g.AddEdge(i,j+(1<<m),dp[i]);
			}
		}
		for(int i=0;i<m;i++){
			int x;
			scanf("%d",&x);
			g.AddEdge(i+(1<<m),T,x);
		}
		int ans=g.Maxflow(S,T);
		if(ans==n) puts("YES");
		else puts("NO");
	}
	return 0;
}

思路

1.使用hungray模版
建好图和容量w 带入模版即可
注意本题中点和边的上限以及数组开的大小
2.注意n的个数就可以注意到普通的网络流建图会t 我们考虑状态压缩
由于m只有10 可以用1<<10来表示每个状态
那n个人压缩成1<<m种人
用dp[i]表示i种类人有多少个，加入超级源点s，s指向所有种类人，容量为该类人个数dp[i]；每种人指向他所能去的星球，容量为该种人数量dp[i]；
加入超级汇点t，所有的星球指向t，容量给星球的容量w

hihocoder 1393

题目要求

班级参加运动会 每个人擅长某些项目 每个人最多参加某个数量的项目 每个项目必须有某个数量的人参加
问是否存在某种匹配使得满足这些条件 即满足多重匹配

参考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 210
#define inf 0x3f3f3f3f
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;
  }
};
Dinic g;
int main(){
//	freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t; cin>>t;
	while(t--){
		int nn,mm;
		cin>>nn>>mm;
		g.ClearAll(maxn);
		int sum=0;
		for(int i=1;i<=mm;i++){
			int x; cin>>x;
			sum+=x;
			g.AddEdge(nn+i,nn+mm+1,x);
		}
		for(int i=1;i<=nn;i++){
			int x,y;
			cin>>x>>y;
			g.AddEdge(0,i,x);
			while(y--){
				int z; cin>>z;
				g.AddEdge(i,nn+z,1);
			}
		}
		if(g.Maxflow(0,nn+mm+1)==sum) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;	
	}
	return 0;
}

思路

建图如下

A对应的是学生 B对应的是项目 a[i]对应的是每个学生限制参加的项目个数 m[i]对应每个项目限制参加的人数 增加一个源点S和一个汇点T
根据a[i]，在s和A[i]之间连接一条容量为a[i]的边
将原来A[i]-B[j]直接的边都改造为从A[i]到B[j]的容量为1的边
最后我们还要连接所有的B[j]-t。由于比赛项目B[j]最多只需要m[j]名选手参加，所以我们不妨限制B[j]-t的容量为m[j]
在完成最大流后，这个网络流图的流量情况直接对应了一个分配方案：
s-A[i]：这一类边的流量表示了A[i]参加的项目数量。
A[i]-B[j]：这一类边的流量表示了A[i]是否参加项目B[j]，若参加则流量为1，否则流量为0。
B[j]-t：这一类边的流量表示了参加比赛项目B[j]的选手数量。
由于流网络会自动调整去满足最大流量，所以它会自动调整每个A[i]-B[j]的流量来使得B[j]-t尽可能大。
若每个项目都能够满足人数的话，网络流会自己调整为所有B[j]-t都满流的情况。
只需要最后判断一下每一条B[j]-t的边是否满流，就可以知道能否满足需求

最小路径覆盖

hihocoder 1394

参考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 1050
#define inf 0x3f3f3f3f
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;
  }
};
Dinic g;
int nn,mm;
int main(){
//	freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	while(cin>>nn>>mm){
		g.ClearAll(maxn);
		int S=0,T=nn+nn+1;
		for(int i=1;i<=nn;i++) g.AddEdge(S,i,1);
		for(int i=nn+1;i<=2*nn;i++) g.AddEdge(i,T,1);
		for(int i=1;i<=mm;i++){
			int u,v;
			cin>>u>>v;
			g.AddEdge(u,nn+v,1);
		}
		cout<<nn-g.Maxflow(S,T)<<endl;
	}
	return 0;
}

思路

这是求最大匹配数用dinic模版 源点到A和B到汇点的容量上限全部设为1即可

最大权闭合子图

hihocoder 1395

题目要求

周末，小Hi和小Ho所在的班级决定举行一些班级建设活动。
根据周内的调查结果，小Hi和小Ho一共列出了N项不同的活动(编号1..N)，第i项活动能够产生a[i]的活跃值。
班级一共有M名学生(编号1..M)，邀请编号为i的同学来参加班级建设活动需要消耗b[i]的活跃值。
每项活动都需要某些学生在场才能够进行，若其中有任意一个学生没有被邀请，这项活动就没有办法进行。
班级建设的活跃值是活动产生的总活跃值减去邀请学生所花费的活跃值。
小Hi和小Ho需要选择进行哪些活动，来保证班级建设的活跃值尽可能大。
比如有3项活动，4名学生：
第1项活动产生5的活跃值，需要编号为1、2的学生才能进行；
第2项活动产生10的活跃值，需要编号为3、4的学生才能进行；
第3项活动产生8的活跃值，需要编号为2、3、4的学生才能进行。
编号为1到4的学生需要消耗的活跃值分别为6、3、5、4。
假设举办活动集合为{1}，需要邀请的学生集合为{1,2}，则得到的班级活跃值为5-9 = -4。
假设举办活动集合为{2}，需要邀请的学生集合为{3,4}，则得到的班级活跃值为10-9 = 1。
假设举办活动集合为{2,3}，需要邀请的学生集合为{2,3,4}，则得到的班级活跃值为18-12 = 6。
假设举办活动集合为{1,2,3}，需要邀请的学生集合为{1,2,3,4}，则得到的班级活跃值为23-18 = 5。
小Hi和小Ho总是希望班级活跃值越大越好，因此在这个例子中，他们会选择举行活动2和活动3。

参考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 450
#define inf 0x3f3f3f3f
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;
  }
};
Dinic g;
int nn,mm;
int main(){
//	freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	while(cin>>nn>>mm){
		g.ClearAll(maxn);
		int s=0,t=nn+mm+1;
		int sum=0;
		for(int i=1;i<=mm;i++){
			int x;
			cin>>x;
			if(x==0) continue;
			g.AddEdge(nn+i,t,x);
		}
		for(int i=1;i<=nn;i++){
			int x,y;
			cin>>x>>y;
			sum+=x;
			g.AddEdge(s,i,x);
			while(y--){
				int z;
				cin>>z;
				g.AddEdge(i,nn+z,inf);
			}
		}
		cout<<sum-g.Maxflow(s,t)<<endl;
	}
	return 0;
}

思路

问题可以转换成求最大权闭合子图
进而转换为所有权值为正的和sum-最小割=sum-最大流
闭合子图：给定一个有向图，从中选择一些点组成一个点集V。对于V中任意一个点，其后续节点都仍然在V中
把这次的问题转化为2分图。将N个活动看作A部，将M个学生看作B部。若第i个活动需要第j个学生，就连一条从A[i]到B[j]的有向边

假如选择A[1]，则我们需要同时选择B[1],B[2]。选择什么活动和其需要的学生，就刚好对应了这个图中的一个闭合子图
首先建立源点s和汇点t，将源点s与所有权值为正的点相连，容量为权值；将所有权值为负的点与汇点t相连，容量为权值的绝对值；权值为0的点不做处理；同时将原来的边容量设置为无穷大。
建好图后，最大权闭合子图的权值等于所有正权点之和减去最小割。

HDU 5988(浮点型MCMF+概率变形)

题目要求

n个点 m条边 每个点里有一些人 会分到一些面包 没有面包吃的人会移动到别的点 每次移动对该边有pi的概率破坏网络
第一个在该条边移动的人不会破坏网络 每条变最多能移动固定的人数 问破坏网络最小的概率是多少

参考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 maxn 250
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-8;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
struct Edge{
	int from,to,cap,flow;
	double cost;
	Edge(int from,int to,int cap,int flow,double 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],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;
int a[maxn],b[maxn],c[maxn];
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		int nn,mm;
		cin>>nn>>mm;
		mc.init(maxn-1);
		for(int i=0;i<nn;i++){
			cin>>a[i]>>b[i];
			c[i]=a[i]-b[i];
		}
		for(int i=0;i<mm;i++){
			int u,v,f;
			double p;
			cin>>u>>v>>f>>p;
			p=-log(1.0-p);
			if(f==0) continue;
			if(f==1) mc.AddEdge(u,v,1,0);
			if(f>1){
				mc.AddEdge(u,v,1,0);
				mc.AddEdge(u,v,f-1,p);
			}
		}
		int S=0,T=nn+1;
		for(int i=0;i<nn;i++){
			if(c[i]==0) continue;
			if(c[i]<0) mc.AddEdge(i+1,T,-c[i],0);
			if(c[i]>0) mc.AddEdge(S,i+1,c[i],0);
		}
		double Cost=mc.Mincost(S,T);
		Cost=exp(-Cost);
		printf("%.2lf\n",1.0-Cost);
	}
	return 0;
}

思路

浮点最小费用最大流
注意MCMF的模版cost和数组d改成duoble型 如果最大流量也是浮点型也需改成double
破坏网络最小的概率=不破坏网络最大的概率
每条边要拆成两条边 第一次经过的时候破坏概率为0
概率乘法加ln变成加法 由于ln一个小数为负数所以添一个负号 转换后套用MCMF浮点型的板子
最后对数变回来即可

HDU 4862(带权最小k路径覆盖)

题目要求

给定一个n*m的矩形(n,m≤10),每个矩形中有一个0~9的数字。
一共可以进行k次游戏，每次游戏可以任意选取一个没有经过的格子为起点，并且跳任意多步，每步可以向右方和下方跳。每次跳需要消耗两点间的曼哈顿距离减一的能量，若每次跳的起点和终点的数字相同，可以获得该数字的能量。（能量可以为负）
询问k次或更少次游戏后是否可以经过所有的格子，若可以求出最大的剩余能量。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<bits/stdc++.h>
#define maxn 250
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int mark[15][15],a[15][15],flag=1;
int num;
struct Edge{
	int from,to,cap,flow,cost;
	Edge(int from,int to,int cap,int flow,int cost):from(from),to(to),cap(cap),flow(flow),cost(cost){}
};
struct MCMF{
	int n,m,s,t;
	vector<Edge>edges;
	vector<int>G[maxn];
	int inq[maxn],d[maxn],p[maxn],a[maxn];
	void init(int n){
		this->n=n;
		for(int i=0;i<n;i++) G[i].clear();
		edges.clear();
	}
	void AddEdge(int from,int to,int cap,int cost){
		edges.push_back(Edge(from,to,cap,0,cost));
		edges.push_back(Edge(to,from,0,0,-cost));
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	bool BellmanFord(int s,int t,int &flow,int& cost){
		for(int i=0;i<n;i++) d[i]=inf;
		memset(inq,0,sizeof(inq));
		d[s]=0,inq[s]=1,p[s]=0,a[s]=inf;
		queue<int>Q;
		Q.push(s);
		while(!Q.empty()){
			int u=Q.front();  Q.pop();
			inq[u]=0;
			for(int i=0;i<G[u].size();i++){
				Edge& e=edges[G[u][i]];
				if(e.cap>e.flow && d[e.to]>d[u]+e.cost){
					d[e.to]=d[u]+e.cost;
					p[e.to]=G[u][i];
					a[e.to]=min(a[u],e.cap-e.flow);
					if(!inq[e.to]){
						Q.push(e.to);
						inq[e.to]=1;
					}
				}
			}
		}
		if(d[t]==inf) return false;
		flow+=a[t];
		cost+=d[t]*a[t];
		int u=t;
		while(u!=s){
			edges[p[u]].flow+=a[t];
			edges[p[u]^1].flow-=a[t];
			u=edges[p[u]].from;
		}
		return true;
	}
	void Mincost(int s,int t){
		int flow=0,cost=0;
		while(BellmanFord(s,t,flow,cost));
		if(flow==num) cout<<-cost<<endl;
		else cout<<"-1"<<endl;
	}
}g;
void creat_map(){
	int nn,mm,k;
	cin>>nn>>mm>>k;
	num=0;
	for(int i=1;i<=nn;i++){
		string s;
		cin>>s;
		for(int j=0;j<s.length();j++){
			a[i][j+1]=s[j]-'0';
			mark[i][j+1]=++num;
		}
	}
	int S=0,T=2*num+2;
	g.AddEdge(S,T-1,k,0);
	for(int i=1;i<=nn;i++){
		for(int j=1;j<=mm;j++){
			g.AddEdge(S,mark[i][j],1,0);
			g.AddEdge(mark[i][j]+num,T,1,0);
			g.AddEdge(T-1,mark[i][j]+num,1,0);
		}
	}
	for(int i=1;i<=nn;i++){
		for(int j=1;j<=mm;j++){
			for(int k=1;k<=nn;k++){
				for(int l=1;l<=mm;l++){
					if((i==k && l>j)||(j==l && i<k)){
						int x=abs(i-k)+abs(j-l)-1;
						if(a[i][j]==a[k][l]) x-=a[i][j];
						g.AddEdge(mark[i][j],mark[k][l]+num,1,x);
					}
				}
			}
		}
	}
	g.Mincost(S,T);
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		g.init(maxn);
		cout<<"Case "<<flag++<<" : ";
		creat_map();
	}
	return 0;
}

思路

带权值的最小K路径覆盖(最小路径覆盖数=总节点数-最大匹配数)
将n*m个点，每个点拆成两个，X，Y
由S向X连容量为1费用为0的边，Y向T连容量为1费用为0的边，X向可到达的Y连容量为1费用为所消耗能量
这样直接跑可求出最大匹配数 所有未流满的Y点数量即为最小路径覆盖数
考虑如何实现K路径覆盖
新建一个点Q,由S向Q连容量为k费用为0的边，有Q向Y连容量为1费用为0的边 即表示可以新增的起点数为k
这样跑一遍最小费用最大流，若不是满流则说明无解
注意：原题中求最大剩余量加负才能套用MCMF模版(最小费用)

HDU 1569(二分图带权最大独立集)

题目要求

给你一个m*n的格子的棋盘，每个格子里面有一个非负数。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取数所在的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
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
#include<bits/stdc++.h>
#define maxn 2505
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int a[51][51];
int mark[51][51],num;
int dirx[4]={0,0,1,-1};
int diry[4]={1,-1,0,0};
struct Edge{
  int from, to, cap, flow;
  Edge(int from,int to,int cap,int flow):from(from),to(to),cap(cap),flow(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);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int nn,mm;
	while(cin>>nn>>mm){
		int sum=0;
		num=0;
		g.ClearAll(maxn);
		for(int i=1;i<=nn;i++){
			for(int j=1;j<=mm;j++){
				cin>>a[i][j];
				sum+=a[i][j];
				mark[i][j]=++num;
			}
		}
		int S=0,T=nn*mm+1;
		for(int i=1;i<=nn;i++){
			for(int j=1;j<=mm;j++){
				if((i+j)%2==0) g.AddEdge(S,mark[i][j],a[i][j]);
				else if((i+j)%2==1) g.AddEdge(mark[i][j],T,a[i][j]);
			}
		}
		for(int i=1;i<=nn;i++){
			for(int j=1;j<=mm;j++){
				if((i+j)%2==0){
					for(int k=0;k<4;k++){
						int xx=i+dirx[k];
						int yy=j+diry[k];
						if(xx>=1 && xx<=nn && yy>=1 && yy<=mm)
							g.AddEdge(mark[i][j],mark[xx][yy],inf);
					}
				}
			}
		}
		int ans=g.Maxflow(S,T);
		cout<<sum-ans<<endl;
	}
	return 0;
}

思路

注意建边
最大带权独立集合=总权值-最小顶点覆盖=总权值-最大匹配数
最大匹配数用dinic
蓝书P367

HDU 4940(无源无汇有下界可行流)

题目要求

给你一个强连通的有向简单图，每条边有D, B两个权值，设S为点集的一个非空真子集
问：是否对于任意的集合S,都有sum (D(i, j)）<= sum(D(j, i) + B(j, i))
i,j表示割边

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

思路

新建源点，汇点，sum[i]为每个点流入的下界流之和减去流出的下界流之和，如果sum[i] > 0，由源点向该点建一条边，上界为sum[i]，下界为0
如果sum[i] < 0, 由该点向汇点建边，上界为-sum[i]，下界为0。
两点之间以B作为流量上限
跑一遍源点到汇点的最大流，当所有源点连的边都满流的时候存在可行流，当前的流量即为最大流。
本题：
将D值作为边的下界，D + B作为边的上界，如果存在可行流，那么对于任意集合S
都有流量小于等于边的容量上界，大于等于边的容量下界，即D(i, j) <= f(i, j) <= D(j, i)+B(j, i)
详解转跳链接

本文标题:网络流拓展一

文章作者:Hippopmonkey

发布时间:2017-06-23, 09:23:51

最后更新:2017-09-16, 14:50:26

原始链接:http://xuboming8.github.io/2017/06/23/网络流拓展/

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

文章目录
  1. 1. 二分图多重匹配
    1. 1.1. HDU 3605
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码(多重匹配hungary模版)
      3. 1.1.3. 参考AC代码(dinic)
      4. 1.1.4. 思路
    2. 1.2. hihocoder 1393
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
  2. 2. 最小路径覆盖
    1. 2.1. hihocoder 1394
      1. 2.1.1. 参考AC代码
      2. 2.1.2. 思路
  3. 3. 最大权闭合子图
    1. 3.1. hihocoder 1395
      1. 3.1.1. 题目要求
      2. 3.1.2. 参考AC代码
      3. 3.1.3. 思路
  4. 4. HDU 5988(浮点型MCMF+概率变形)
    1. 4.1. 题目要求
    2. 4.2. 参考AC代码
    3. 4.3. 思路
  5. 5. HDU 4862(带权最小k路径覆盖)
    1. 5.1. 题目要求
    2. 5.2. 参考AC代码
    3. 5.3. 思路
  6. 6. HDU 1569(二分图带权最大独立集)
    1. 6.1. 题目要求
    2. 6.2. 参考AC代码
    3. 6.3. 思路
  7. 7. HDU 4940(无源无汇有下界可行流)
    1. 7.1. 题目要求
    2. 7.2. 参考AC代码
    3. 7.3. 思路
|