题目传送门:这里
裸的最大流,复习了下EK算法,好吧,掌握的还是最慢的算法。。。。。EK比较好明白。。。。。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define inf 1<<29 using namespace std; int m,n,a,b,c; int p[205][205]; int pre[205]; bool v[205]; bool bfs(int s,int t)//搜索增广路径 { memset(v,0,sizeof(v)); int r; queue<int>q; q.push(s); v[s]=1; while(!q.empty()) { r=q.front(); q.pop(); for(int i=1;i<=m;i++) { if(p[r][i]>0&&v[i]==0) { pre[i]=r; if(i==t)return true; q.push(i); v[i]=1; } } } return false; } int ek(int s,int t) { int f=0; int mf; while(bfs(s,t)) { mf=inf; for(int i=t;i!=s;i=pre[i])mf=p[pre[i]][i]<mf?p[pre[i]][i]:mf;//找到增广路径上的残留网络最小的一段 for(int i=t;i!=s;i=pre[i]) { p[pre[i]][i]-=mf; p[i][pre[i]]+=mf; } f+=mf; } return f; } int main() { while(scanf("%d%d",&n,&m)!=EOF) { memset(p,0,sizeof(p)); for(int i=0;i<n;i++) { scanf("%d%d%d",&a,&b,&c); p[a][b]+=c; } cout<<ek(1,m)<<endl; } return 0; }