363 网络流 最小割 Dinic 算法
视频链接：https://www.bilibili.com/video/BV1iG411s7iX///Luogu P1344 追查坏牛奶Pollutant Control#include #include #include #include #define N 10010#define M 200010using namespace std;int n,m,S,T;int a,b,c;struct edge{int v,c,ne;}e;int h,idx=1; //从2,3开始配对int d,cur,vis;void add(int a,int b,int c){e[++idx]={b,c,h};h=idx;}bool bfs(){ //对点分层，找增广路memset(d,0,sizeof d);queueq; q.push(S); d=1;while(q.size()){ int u=q.front(); q.pop(); for(int i=h;i;i=e.ne){ int v=e.v; if(d==0 && e.c){ d=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==d+1 && e.c){ int f=dfs(v,min(mf,e.c)); e.c-=f; e.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
页:
[1]