本文主要是介绍UVa10330 Power Transmission，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给出了图中每个顶点和每条边的流量限制，求最大流。
思路：增广路算法。话说这是白书给的第一道最大流，就不是最简单的那种。。顶点还有流量限制。于是拆点，把每个点拆成两个，一个进一个出，两个点之间连边，限制就是点原来的限制。
这也是本人第一道最大流，我的理解是这样的：建好图以后，开始BFS找增广路，每一次都那样找，只要发现能从源点流到汇点，就把流加进去，直到找不到了，就是最大流。
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <memory.h>
#include <vector>
#include <queue>
#include <stack>
#include <ctype.h>
#define INF 1000000000
using namespace std;const int maxn=210;int n;
int m;int a[maxn];
int c[maxn][maxn];
int f[maxn][maxn];
int p[maxn];int main(){while(cin>>n){memset(c,0,sizeof(c));memset(f,0,sizeof(f));for(int i=1;i<=n;i++){cin>>c[2*i][2*i+1];}cin>>m;int u,v,w;for(int i=1;i<=m;i++){cin>>u>>v>>w;c[2*u+1][2*v]=w;}int b,d;cin>>b>>d;for(int i=1;i<=b;i++){int t;cin>>t;c[1][2*t]=INF;}for(int i=1;i<=d;i++){int t;cin>>t;c[2*t+1][2*n+2]=INF;}int ans=0;while(true){//找增广路 memset(a,0,sizeof(a));a[1]=INF;queue<int> que;que.push(1);while(!que.empty()){int cur=que.front();que.pop();for(int i=1;i<=2*n+2;i++){if((c[cur][i]>f[cur][i])&&!a[i]){int t=min(c[cur][i]-f[cur][i],a[cur]);a[i]=t;p[i]=cur;if(t)que.push(i);if(i==(2*n+2))break;}}}if(!a[2*n+2]){break;}ans+=a[2*n+2];for(int i=2*n+2;i!=1;i=p[i]){f[p[i]][i]+=a[2*n+2];f[i][p[i]]-=a[2*n+2];}}cout<<ans<<endl;}return 0;
}这篇关于UVa10330 Power Transmission的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
