圖論總結（9）網絡流問題

說實話網絡流學得很淺，隻能做點水題，沒時間練題了。

下面總結下幾類題型。

一.最大流問題

概述問題就是一個有向圖，每條邊都有個容量，給你源點s和彙點t，問你從s到t的最大流量是多少。

用增廣路算法可以解決

先求出每條邊對應反向邊的殘量，構造出殘量網絡，若殘量網絡中有從s到t的路徑，則s到t存在增廣路（簡單了解為可以是流量變大的路徑），顯然但殘量網絡中不存在增廣路時有最大流量。

EdmondKarp算法

模闆：

const int INF=0X3f3f3f3f;
struct Edge{
	int from,to,cap,flow;
	Edge(int fr,int t,int c,int fl):from(fr),to(t),cap(c),flow(fl){}
};
struct EdmondKarp{
	int n,m;
	vector<Edge>edges;
	vector<int>G[maxn];
	int a[maxn];
	int p[maxn];
	void init(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);  
	}
	int Maxflow(int s,int t){
		int flow=0;
		for(;;){
			memset(a,0,sizeof(a));
			memset(p,0,sizeof(p));
			queue<int>q;
			q.push(s);
			a[s]=INF;
			while(!q.empty()){
				int u=q.front();q.pop();
				for(int i=0;i<G[u].size();i++){
					Edge &e=edges[G[u][i]];
					if(p[e.to]==0&&e.cap>e.flow&&e.to!=s){
						p[e.to]=G[u][i];
						a[e.to]=min(a[u],e.cap-e.flow);
						q.push(e.to);
					}
				}
				if(a[t])break;
			}
			if(!a[t])break;
			for(int u=t;u!=s;u=edges[p[u]].from){
				edges[p[u]].flow+=a[t];
				edges[p[u]^1].flow-=a[t];//反向邊
			}
			flow+=a[t];
		}
		return flow;
	}
};
           

Dinc算法：

EdmondKarp算法太慢，比賽一般不用，紫書中推薦了兩種算法，Dinic和ISPA，個人更喜歡Dinic，ISPA我反正比賽用不到了，時間問題先隻給出Dinic算法

Dinic比EdmandKarp算法的改進在于先用bfs()求出了各個點到源點的層次d（u）；在用dfs()找滿足d（v）=d（u）+1的增廣路。

模闆：

const int INF=0X3f3f3f3f;
struct Edge{
	int from,to,cap,flow;
	Edge(int fr,int t,int c,int fl):from(fr),to(t),cap(c),flow(fl){}
};
struct Dinic{
	int n,m,s,t;
	vector<Edge>edges;
	vector<int>G[maxn];
	int vis[maxn],p[maxn],d[maxn],cur[maxn];
	void init(int n){
		for(int i=1;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));
		int 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;
		d[s]=0;vis[s]=1;
		q.push(s);
		while(!q.empty()){
			int u=q.front();q.pop();
			for(int i=0;i<G[u].size();i++){
				Edge& e=edges[G[u][i]];
				if(!vis[e.to]){
					vis[e.to]=1;
					d[e.to]=d[u]+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[e.to]=d[x]+1&&(f=dfs(e.to,min(a,e.cap-e.flow))>0)){
				a-=f;
				e.flow+=f;
				edges[G[x][i]^1].flow-=f;
				flow+=f;
				if(a==0)break;
			}
		}
		return flow;
	}
	int Maxflow(int s,int t){
		this->s=s;
		this->t=t;
		int flow=0;
		while(bfs()){
			flow+=dfs(s,INF);
		}
		return flow;
	} 
};
           

二.最小費用最大流問題

每條邊加了一個費用，問在總流量最大的前提下最小費用 為多少。

隻需要将Edmond算中求增廣路的方法換為BellmanFord算法求出最小費用的路徑就行了。

bool Bellmanford(int s,int t,int &flow,int cost){
		for(int i=1;i<=n;i++)d[i]=INF;
		memset(vis,0,sizeof(vis));
		d[s]=0;vis[s]=1;p[s]=0;a[s]=INF;
		queue<int>q;
		q.push(s);
		while(!q.empty()){
			int u=q.front();q.pop();
			vis[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){
					p[e.to]=G[u][i];
					d[e.to]=d[u]+e.cost;
					a[e.to]=min(a[u],e.cap-e.flow);
					if(!vis[e.to]){
						q.push(e.to);
						vis[e.to]=1;
					}
					
				}
			}
		}
		if(d[t]==INF)return false;
		flow+=a[t];
		cost+=a[t]*d[t];
		for(int u=t;u!=s;u=edges[p[u]].from){
			edges[p[u]].flow+=a[t];
			edges[p[u]^1].flow-=a[t];
		}
		return true;
	}
	int MincostMaxflow(int s,int t,int &cost){
		int flow=0;cost=0;
		while(Bellmanford(s,t,flow,cost));
		return flow ;
	}
           

還有些小的東西就不說了。

二分圖單獨總結吧，畢竟東西還有點多。