本文主要是介绍poj 1459 zoj 1734 Power Network（最大流），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
电网 中一些节点 可能会消耗电能 提供电能
节点之间有电线传输电能 传输的电能有上限值
节点中没有 源点和汇点 类型的节点
所以需要我们添加源点汇点 n个节点 从0开始 设源点为n+1 汇点为n+2
源点到每个电站之间添加一条边 权值为该电站能够提供的电能
每个消费者与汇点之间添加一条边 权值为该消费者消费的电能
根据所给的 电线中的起点和重点 添加边 权值为该电线能够传输电能的最大值
然后就是读取数据 先把(字符之前所有的字符 读掉 然后读入括号中的数
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <queue>#define eps 1e-8
#define op operator
#define MOD 10009
#define MAXN 110
#define INF 0x7fffffff
#define MEM(a,x) memset(a,x,sizeof a)
#define ll __int64using namespace std;struct Dinic
{struct Edge{int from,to,cap,flow;Edge(){}Edge(int from,int to,int cap,int flow):from(from),to(to),cap(cap),flow(flow){}};vector<Edge> edges;vector<int> G[MAXN];bool vis[MAXN];int d[MAXN];int cur[MAXN];int n,m,s,t,maxflow;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){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(){MEM(vis,0);MEM(d,-1);queue<int> q;q.push(s);d[s]=maxflow=0;vis[s]=1;while(!q.empty()){int u=q.front(); q.pop();int sz=G[u].size();for(int i=0;i<sz;i++){Edge e=edges[G[u][i]];if(!vis[e.to]&&e.cap>e.flow){d[e.to]=d[u]+1;vis[e.to]=1;q.push(e.to);}}}return vis[t];}int dfs(int u,int a){if(u==t||a==0) return a;int sz=G[u].size();int flow=0,f;for(int &i=cur[u];i<sz;i++){Edge &e=edges[G[u][i]];if(d[u]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0){e.flow+=f;edges[G[u][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()){MEM(cur,0);flow+=dfs(s,INF);}return flow;}
}Dic;int main()
{
//freopen("ceshi.txt","r",stdin);int n,np,nc,m;while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF){int s=n+1,t=n+2;Dic.init(n+2);for(int i=0;i<m;i++){int u,v,w;while(getchar()!='(');scanf("%d,%d)%d",&u,&v,&w);Dic.addedge(u,v,w);}for(int i=0;i<np;i++){int v,w;while(getchar()!='(');scanf("%d)%d",&v,&w);Dic.addedge(s,v,w);}for(int i=0;i<nc;i++){int u,w;while(getchar()!='(');scanf("%d)%d",&u,&w);Dic.addedge(u,t,w);}printf("%d\n",Dic.Maxflow(s,t));}return 0;
}
这篇关于poj 1459 zoj 1734 Power Network（最大流）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
