网络流专题

自用笔记算法

网络流专题

EK算法(最大流)

增广路定理

紫书P367-368

模版一(存在重边)

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
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 250
using namespace std;
int n,m,k;
int s,t;
struct node{
	int from,to,cap,flow;
	node(int from,int to,int cap,int flow):from(from),to(to),cap(cap),flow(flow){}
};
vector<node>edge;
int g[maxn][maxn];
int a[maxn],p[maxn];
void init(){
	memset(g,0,sizeof(g));
	memset(a,0,sizeof(a));
	memset(p,0,sizeof(p));
	edge.clear();
}
void addedge(int from,int to,int cap){
	if(g[from][to]!=0) edge[g[from][to]].cap+=cap;
	else{
		edge.push_back(node(from,to,cap,0));
		edge.push_back(node(to,from,0,0));
		k=edge.size();
		g[from][to]=k-2;
		g[to][from]=k-1;
	}
}
int EdmondsKarp(){
	int flow=0;
	for(;;){
		memset(a,0,sizeof(a));
		queue<int>q;
		q.push(s);
		a[s]=inf;
		while(!q.empty()){
			int x=q.front();
			q.pop();
			for(int i=1;i<=n;i++){
				node e=edge[g[x][i]];
				if(!a[e.to] && e.cap>e.flow){
					p[e.to]=g[x][i];
					a[e.to]=min(a[x],e.cap-e.flow);
					q.push(e.to);
				}
			}
			if(a[t]) break;
		}
		if(!a[t]) break;
		for(int i=t;i!=s;i=edge[p[i]].from){
			edge[p[i]].flow+=a[t];
			edge[p[i]^1].flow-=a[t];
		}
		flow+=a[t];
	}
	return flow;
}
int main(){
//	freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	while(cin>>m>>n){
		init();
		s=1,t=n;
		for(int i=1;i<=m;i++){
			int u,v,w;
			cin>>u>>v>>w;
			addedge(u,v,w);
		}
		cout<<EdmondsKarp()<<endl;
	}
	return 0;
}

模版二(不存在重边)

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
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 250
using namespace std;
int n,m,k;
int s,t;
struct node{
	int from,to,cap,flow;
	node(int from,int to,int cap,int flow):from(from),to(to),cap(cap),flow(flow){}
};
vector<node>edge;
vector<int>g[maxn];
int a[maxn],p[maxn];
void init(int n){
	for(int i=0;i<=n;i++) g[i].clear();
	edge.clear();
	memset(a,0,sizeof(a));
	memset(p,0,sizeof(p));
}
void addedge(int from,int to,int cap){
	edge.push_back(node(from,to,cap,0));
	edge.push_back(node(to,from,0,0));
	k=edge.size();
	g[from].push_back(k-2);
	g[to].push_back(k-1);
}
int EdmondsKarp(){
	int flow=0;
	for(;;){
		memset(a,0,sizeof(a));
		queue<int>q;
		q.push(s);
		a[s]=inf;
		while(!q.empty()){
			int x=q.front();
			q.pop();
			for(int i=0;i<g[x].size();i++){
				node e=edge[g[x][i]];
				if(!a[e.to] && e.cap>e.flow){
					p[e.to]=g[x][i];
					a[e.to]=min(a[x],e.cap-e.flow);
					q.push(e.to);
				}
			}
			if(a[t]) break;
		}
		if(!a[t]) break;
		for(int i=t;i!=s;i=edge[p[i]].from){
			edge[p[i]].flow+=a[t];
			edge[p[i]^1].flow-=a[t];
		}
		flow+=a[t];
	}
	return flow;
}
int main(){
	freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	while(cin>>m>>n){
		init(n);
		s=1,t=n;
		for(int i=1;i<=m;i++){
			int u,v,w;
			cin>>u>>v>>w;
			addedge(u,v,w);
		}
		cout<<EdmondsKarp()<<endl;
	}
	return 0;
}

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
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 ClearFlow(){
    for(int i=0;i<edges.size();i++) edges[i].flow=0;    
}
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;
}
void Reduce(){   
    for(int i=0;i<edges.size();i++) edges[i].cap-=edges[i].flow;
  }
}g;

最短增广路模版

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
const int MAX = 0x5fffffff;//
int tab[250][250];//邻接矩阵 
int dis[250];//距源点距离,分层图 
int q[2000], h, r;//BFS队列 ,首,尾 
int N, M, ANS;N:///点数;M,边数 
int BFS()
{
    int i, j;
    memset(dis, 0xff, sizeof(dis));//以-1填充 
    dis[1] = 0;
    h = 0; r = 1;
    q[1] = 1;
    while (h<r)
    {
        j = q[++h];
        for (i = 1; i <= N; i++)
            if (dis[i]<0 && tab[j][i]>0)
            {
                dis[i] = dis[j] + 1;
                q[++r] = i;
            }
    }
    if (dis[N]>0)
        return 1;
    else
        return 0;//汇点的DIS小于零,表明BFS不到汇点 
}
//Find代表一次增广,函数返回本次增广的流量,返回0表示无法增广 
int find(int x, int low)//Low是源点到现在最窄的(剩余流量最小)的边的剩余流量
{
    int i, a = 0;
    if (x == N)return low;//是汇点 
    for (i = 1; i <= N; i++)
        if (tab[x][i] >0 //联通 
            && dis[i] == dis[x] + 1 //是分层图的下一层 
            && (a = find(i, min(low, tab[x][i]))))//能到汇点(a <> 0) 
        {
            tab[x][i] -= a;
            tab[i][x] += a;
            return a;
        }
    return 0;
}
int Dinic()
{
    int ANS = 0, tans;
    while (BFS())//要不停地建立分层图,如果BFS不到汇点才结束 
    {
        while (tans = find(1, 0x7fffffff))ANS += tans;//一次BFS要不停地找增广路,直到找不到为止 
    }
}

ISAP(最大流)

模版

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 550
#define inf 0x3f3f3f3f
using namespace std;
struct Edge{
  int from, to, cap, flow;
};
struct ISAP{
  int n, m, s, t;
  vector<Edge> edges;
  vector<int> G[maxn];   
  bool vis[maxn];        
  int d[maxn];           
  int cur[maxn];       
  int p[maxn];         
  int num[maxn];       
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(t);
    vis[t] = 1;
    d[t] = 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]^1];
        if(!vis[e.from] && e.cap > e.flow) {
          vis[e.from] = 1;
          d[e.from] = d[x] + 1;
          Q.push(e.from);
        }
      }
    }
    return vis[s];
}
void ClearAll(int n){
    this->n = n;
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
}
int Augment(){
    int x = t, a = inf;
    while(x != s) {
      Edge& e = edges[p[x]];
      a = min(a, e.cap-e.flow);
      x = edges[p[x]].from;
    }
    x = t;
    while(x != s) {
      edges[p[x]].flow += a;
      edges[p[x]^1].flow -= a;
      x = edges[p[x]].from;
    }
    return a;
}
int Maxflow(int s, int t){
    this->s = s; this->t = t;
    int flow = 0;
    BFS();
    memset(num, 0, sizeof(num));
    for(int i = 0; i < n; i++) num[d[i]]++;
    int x = s;
    memset(cur, 0, sizeof(cur));
    while(d[s] < n) {
      if(x == t) {
        flow += Augment();
        x = s;
      }
      int ok = 0;
      for(int i = cur[x]; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i]];
        if(e.cap > e.flow && d[x] == d[e.to] + 1) { 
          ok = 1;
          p[e.to] = G[x][i];
          cur[x] = i; 
          x = e.to;
          break;
        }
      }
      if(!ok) { 
        int m = n-1; 
        for(int i = 0; i < G[x].size(); i++) {
          Edge& e = edges[G[x][i]];
          if(e.cap > e.flow) m = min(m, d[e.to]);
        }
        if(--num[d[x]] == 0) break;
        num[d[x] = m+1]++;
        cur[x] = 0; 
        if(x != s) x = edges[p[x]].from;
      }
    }
    return flow;
}
};
ISAP g;
int main(){
//	freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t,flag=1; cin>>t;
	while(t--){
		int x,y;
		cin>>x>>y;
		g.ClearAll(x);
		for(int i=1;i<=y;i++){
			int u,v,w;
			cin>>u>>v>>w;
			g.AddEdge(u,v,w);
		}
		cout<<"Case "<<flag++<<": "<<g.Maxflow(1,x)<<endl;	
	}
	return 0;
}

MCMF(最小费用最大流)

模版

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
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;
	}
};

MCMF(最小费用循环流 寻找负费用增广圈)

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
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 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){
                    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(double & cost){
        double flow=0;cost=0;
        while(BellmanFord(n,flow,cost));
        return flow;
    }
}g;

HUD 1533(MCMF解法)

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 inf 0x3f3f3f3f
#define maxn 250
using namespace std;
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 node{
	int x,y;
}man[maxn],house[maxn];
int m_cnt,h_cnt;
int S,T;
int x,y;
int dis(int x1,int y1,int x2,int y2){
	return abs(x1-x2)+abs(y1-y2);
}
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;
	}
};
MCMF g;
void creatmap(){
	m_cnt=0,h_cnt=0;
	memset(man,0,sizeof(man));
	memset(house,0,sizeof(house));
	for(int i=0;i<x;i++){
		string st;
		cin>>st;
		for(int j=0;j<st.length();j++){
			if(st[j]=='H'){
				h_cnt++;
				house[h_cnt].x=i+1;
				house[h_cnt].y=j+1;	
			}
			else if(st[j]=='m'){
				m_cnt++;
				man[m_cnt].x=i+1;
				man[m_cnt].y=j+1;
			}
		}
	}
	S=0,T=h_cnt+m_cnt+1;
	g.init(h_cnt+m_cnt+2);
	for(int i=1;i<=h_cnt;i++) g.AddEdge(S,i,1,0);
	for(int i=1;i<=m_cnt;i++) g.AddEdge(i+h_cnt,T,1,0);
	for(int i=1;i<=h_cnt;i++){
		for(int j=1;j<=m_cnt;j++){
			int d=dis(house[i].x,house[i].y,man[j].x,man[j].y);
			g.AddEdge(i,j+h_cnt,1,d);
		}
	}
}
int main(){
//	freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	while(cin>>x>>y){
		if(x==0 && y==0) break;  
		creatmap();
		cout<<g.Mincost(S,T)<<endl;	
	}
	return 0;
}

最大流最小割

hihocoder 1378

题目要求
求出最小割的容量(等价最大流)
同时求出图G最小割S集合的点数以及集合内点的编号
若有多解输出一组即可

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
#include<bits/stdc++.h>
#define maxn 550
#define inf 0x3f3f3f3f
using namespace std;
int flag,num;
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;
    if(flag) num++; 
    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;
          if(flag==0 && e.to==n) return 1; 
          if(flag) num++;
          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);
    }
	flag=1;
	flag=BFS();
    return flow;
  }
};
Dinic g;
int main(){
	freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	flag=0,num=0;
	int x,y;
	cin>>x>>y;
	g.ClearAll(x);
	for(int i=1;i<=y;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g.AddEdge(u,v,w);
	}
	cout<<g.Maxflow(1,x)<<" ";
	cout<<num<<endl;
	for(int i=1;i<=x;i++){
		if(g.vis[i]){
			if(!flag) flag=1;
			else cout<<" ";
			cout<<i;
		}
	}
	cout<<endl;
	return 0;
}

本文标题:网络流专题

文章作者:Hippopmonkey

发布时间:2017-05-29, 20:26:45

最后更新:2017-10-07, 17:33:24

原始链接:http://xuboming8.github.io/2017/05/29/网络流专题/

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

文章目录
  1. 1. 网络流专题
    1. 1.1. EK算法(最大流)
      1. 1.1.1. 增广路定理
      2. 1.1.2. 模版一(存在重边)
      3. 1.1.3. 模版二(不存在重边)
    2. 1.2. dinic算法(最大流)
      1. 1.2.1. 模版
      2. 1.2.2. 最短增广路模版
    3. 1.3. ISAP(最大流)
      1. 1.3.1. 模版
    4. 1.4. MCMF(最小费用最大流)
      1. 1.4.1. 模版
    5. 1.5. MCMF(最小费用循环流 寻找负费用增广圈)
      1. 1.5.1. HUD 1533(MCMF解法)
    6. 1.6. 最大流最小割
      1. 1.6.1. hihocoder 1378
|