EdmondsKarp模板，hdu1532

本文主要是介绍EdmondsKarp模板，hdu1532，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

模板题。

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#define inf 10000000
#define pi acos(-1.0)
#define eps 1e-8
#define seed 131
using namespace std;
typedef pair<int,int> pii;
typedef unsigned long long ULL;
typedef long long LL;
const int maxn=205;
struct Edge{int from,to,cap,flow;Edge(int a,int b,int c,int d):from(a),to(b),cap(c),flow(d){}
};
int n,m;
vector<Edge> edges;
vector<int> g[maxn];
int a[maxn];//可改进量
int p[maxn];//最短路树上的入弧编号
void init()
{for(int i=0;i<m;i++)g[i].clear();edges.clear();
}
void addEdge(int a,int b,int c)
{edges.push_back(Edge(a,b,c,0));edges.push_back(Edge(b,a,0,0));int m=edges.size();g[a].push_back(m-2);g[b].push_back(m-1);
}
int maxFlow(int s,int t)
{int flow=0;for(;;){memset(a,0,sizeof(a));queue<int>que;que.push(s);a[s]=inf;while(!que.empty()){int u=que.front();que.pop();int len=g[u].size();for(int i=0;i<len;i++){Edge& e=edges[g[u][i]];if(!a[e.to]&&e.cap>e.flow){p[e.to]=g[u][i];a[e.to]=min(a[u],e.cap-e.flow);que.push(e.to);}}if(a[t])break;}if(a[t]==0)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;
}
int main()
{int a,b,c;while(~scanf("%d%d",&n,&m)){init();for(int i=0;i<n;i++){scanf("%d%d%d",&a,&b,&c);addEdge(a,b,c);}cout<<maxFlow(1,m)<<endl;}return 0;
}

这篇关于EdmondsKarp模板，hdu1532的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---