本文主要是介绍HDU 4280 Island Transport 网络流，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给你一些点，自己找最左边的点为起点，最右边的点位终点，给你边的权值，求最大流，dinic就可以过。
思路：dinic，建无向图，正反向flow一样。
#pragma comment(linker,"/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define inf 0x7fffffff
using namespace std;
const int N=100000+5;
int n,m;
int s,t;
struct node
{int v,next,flow;
}e[N*2];
int head[N],cnt;
void Init()
{memset(head,-1,sizeof(head));cnt=0;
}
void add(int a,int b,int c)
{e[cnt].v=b;e[cnt].flow=c;e[cnt].next=head[a];head[a]=cnt++;
}
class Dinic
{public:int spath(){queue<int>q;while(!q.empty()) q.pop();memset(dis,-1,sizeof(dis));dis[s]=0;q.push(s);while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i+1;i=e[i].next){int v=e[i].v;if(dis[v]==-1&&e[i].flow>0){dis[v]=dis[u]+1;q.push(v);if(v==t) return 1;}}}return 0;}int Min(int a,int b){if(a<b) return a;return b;}int dfs(int u,int flow){int cost=0;if(u==t) return flow;for(int i=head[u];i+1;i=e[i].next){int v=e[i].v;if(dis[v]==dis[u]+1&&e[i].flow>0){if(cost==flow) return cost;int min=dfs(v,Min(e[i].flow,flow-cost));e[i].flow-=min;e[i^1].flow+=min;cost+=min;if(cost==flow) return cost;}}if(cost==0){dis[u]=0;}return cost;}int result(){int res=0;while(spath()){res+=dfs(s,inf);}return res;}private:int dis[N];
}dinic;
void Input()
{int maxx=-inf,minn=inf;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int x,y;scanf("%d%d",&x,&y);if(maxx<x){maxx=x;t=i;} if(minn>x){minn=x;s=i;}} for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);}
}
void treatment()
{printf("%d\n",dinic.result());
}
int main()
{int t;scanf("%d",&t);while(t--){Init(); Input();treatment();}return 0;
}这篇关于HDU 4280 Island Transport 网络流的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
