题意
网络流最大流模板
思路
EK也不会超时
所以说是一个数据比较水的模板题
但是POJ有点坑，多组数据，而且题目没给
哭得我AC率直掉
代码
用的朴素Dinic
#include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; #define N 200010 #define INF 0x3fffffff inline int read() { int x = 0,f = 1; char ch = getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f = -1; ch = getchar(); } while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x * f; } struct point{ int fr,to,val; int nxt; }edge[N]; int head[N]; int cnt; void add_edge(int x,int y,int z) { edge[cnt].fr=x,edge[cnt].to=y,edge[cnt].val=z; edge[cnt].nxt=head[x],head[x]=cnt++; edge[cnt].fr=y,edge[cnt].to=x,edge[cnt].val=0; edge[cnt].nxt=head[y],head[y]=cnt++; } //我放弃链式前向星 int n,m,st,ed; int deep[N]; int BFS() { queue<int>q; memset(deep,0,sizeof(deep)); q.push(st); deep[st]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=edge[i].nxt) { int tmp=edge[i].to; if(edge[i].val<=0 || deep[tmp]) continue; deep[tmp]=deep[u]+1; q.push(tmp); } } return deep[ed]; } int ans; int dfs(int u,int flow)//flow为到达终点最多能增广的值 { if(u==ed) return flow; int add=0; for(int i=head[u];i!=-1&&add<flow;i=edge[i].nxt) { int v=edge[i].to; if(deep[v]!=deep[u]+1) continue; if(!edge[i].val) continue;//剪枝 int tmpadd=dfs(v,min(edge[i].val,flow-add)); edge[i].val-=tmpadd; edge[i^1].val+=tmpadd;//sub add+=tmpadd; } return add; } void Dinic() { while(BFS()) ans+=dfs(st,INF); } int main() { while(scanf("%d%d",&n,&m)==2) { ans=0; st=1,ed=m; memset(edge,0,sizeof(edge)); memset(head,-1,sizeof(head)); for(int i=1,u,v,co;i<=n;i++) { u=read(),v=read(),co=read(); add_edge(u,v,co); } Dinic(); printf("%d ",ans); } return 0; }