IT评测·应用市场-qidao123.com

标题: 363 网络流 最小割 Dinic 算法 [打印本页]

---

作者: 前进之路    时间: 2022-8-10 14:07
标题: 363 网络流 最小割 Dinic 算法
视频链接：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

---

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)

Powered by Discuz! X3.4