视频链接：https://www.bilibili.com/video/BV1iG411s7iX/
[code]//Luogu P1344 [USACO4.4]追查坏牛奶Pollutant Control#include #include #include #include #define N 10010#define M 200010using namespace std;int n,m,S,T;int a[N],b[N],c;struct edge{int v,c,ne;}e[M];int h[N],idx=1; //从2,3开始配对int d[N],cur[N],vis[N];void add(int a,int b,int c){ e[++idx]={b,c,h[a]}; h[a]=idx;}bool bfs(){ //对点分层，找增广路 memset(d,0,sizeof d); queueq; q.push(S); d[S]=1; while(q.size()){ int u=q.front(); q.pop(); for(int i=h;i;i=e.ne){ int v=e.v; if(d[v]==0 && e.c){ d[v]=d+1; q.push(v); if(v==T)return true; } } } return false;}int dfs(int u, int mf){ //多路增广 if(u==T) return mf; int sum=0; for(int i=cur;i;i=e.ne){ cur=i; //当前弧优化 int v=e.v; if(d[v]==d+1 && e.c){ int f=dfs(v,min(mf,e.c)); e.c-=f; e[i^1].c+=f; //更新残留网 sum+=f; //累加u的流出流量 mf-=f; //减少u的剩余流量 if(mf==0)break;//余量优化 } } if(sum==0) d=0; //残枝优化 return sum;}int dinic(){ //累加可行流 int flow=0; while(bfs()){ memcpy(cur, h, sizeof h); flow+=dfs(S,1e9); } return flow;}int main(){ scanf("%d%d",&n,&m); S=1,T=n; for(int i=1;i |
