Luogu 2740 Drainage Ditches
題目連結:https://www.luogu.org/problemnew/show/P2740
思路:
裸的網路最大流。因為資料範圍較小,故可以使用演算法,鄰接矩陣存圖直接求解。
演算法原理就是不斷尋找增廣路徑,累加路徑上的最小剩餘流量,直到圖中不存在增廣路。
程式碼:
#include <cstdio> #include <cctype> #include <cstring> #include <iostream> #include <algorithm> #include <queue> static const int INF=1<<30; static const int MAXN=300; using namespace std; queue<int> q; int n,m,u,v,w,maxflow,father[MAXN],res[MAXN],c[MAXN][MAXN],flow[MAXN][MAXN]; inline int read(){ int x=0;bool sign=false; char alpha=0; while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar(); while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar(); return sign?-x:x; } inline int EK(int s,int t){ while(1){ memset(res,0,sizeof(res)); res[s]=INF; q.push(s); while(!q.empty()){ int now=q.front();q.pop(); for(int i=1;i<=m;i++){ if(res[i]==0&&c[now][i]>flow[now][i]){ q.push(i); father[i]=now; res[i]=min(res[now],c[now][i]-flow[now][i]); } } } if(res[t]==0) return maxflow; for(int i=t;i!=s;i=father[i]){ flow[father[i]][i]+=res[t]; flow[i][father[i]]-=res[t]; } maxflow+=res[t]; } } int main(){ n=read();m=read(); for(int i=1;i<=n;i++){ u=read();v=read();w=read(); c[u][v]+=w; } printf("%d\n",EK(1,m)); return 0; }