网络流Dinic模板&&炸点优化&&当前弧优化

佚名 6年前 (2019-05-05) 随笔 1277人围观抢沙发百度已收录

没什么时间，先上模板，内容后面再补

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<queue>
  7 #define pn putchar('\n')
  8 #define pd putchar(' ')
  9 #define num ch-'0'
 10 #define reint register int
 11 using namespace std;
 12 template <typename T>
 13 void read(T &res)
 14 {
 15     char ch;bool flag=false;
 16     while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
 17     for(res=num;isdigit(ch=getchar());res=res*10+num);
 18     flag&&(res=-res);
 19 }
 20 template <typename T>
 21 void write(T x)
 22 {
 23     if(x<0)putchar('-'),x=-x;
 24     if(x>9)write(x/10);
 25     putchar(x%10+'0');
 26 }
 27 typedef long long ll;
 28 const int INF=0x7fffffff;
 29 const int inf=0x3f3f3f3f;
 30 const int mod=1000000007;
 31 const int maxn=1000005;
 32 int cnt=-1,head[maxn],dis[maxn],cur[maxn];
 33 queue<int>que;
 34 int n,m,st,ed;
 35 struct edge{ int to,value,net;}e[maxn<<1];
 36 void add(int from,int to,int value) {
 37     cnt++;
 38     e[cnt].to=to;
 39     e[cnt].value=value;
 40     e[cnt].net=head[from];
 41     head[from]=cnt;
 42 }
 43 int bfs(int st,int ed) {
 44     que=queue<int>();       //清空队列
 45     memset(dis,-1,sizeof(dis));
 46     dis[st]=0;
 47     que.push(st);
 48     while(!que.empty()) {
 49         int x=que.front();
 50         que.pop();
 51         for(reint i=head[x];i>-1;i=e[i].net) {
 52             int now=e[i].to;
 53             if(dis[now]==-1&&e[i].value) {
 54                 que.push(now);
 55                 dis[now]=dis[x]+1;
 56             }
 57         }
 58     }
 59     return dis[ed]!=-1;
 60 }
 61 int dfs(int x,int t,int maxflow) {
 62     if(x==t) return maxflow;
 63     int ans=0;
 64     for(reint i=cur[x];i>-1;i=e[i].net) {       //当前弧优化
 65         int now=e[i].to;
 66         if(dis[now]!=dis[x]+1||e[i].value==0||ans>=maxflow) continue;
 67         cur[x]=i;
 68         int f=dfs(now,t,min(e[i].value,maxflow-ans));
 69         e[i].value-=f;
 70         e[i^1].value+=f;
 71         ans+=f;
 72     }
 73     if(!ans) dis[x]=-1;     //炸点优化
 74     return ans;
 75 }
 76 inline int Dinic(int st,int ed) {
 77     int ans=0;
 78     while(bfs(st,ed)) {
 79         memcpy(cur,head,sizeof(head));
 80         int k;
 81         while((k=dfs(st,ed,INF)))
 82             ans+=k;
 83     }
 84     return ans;
 85 }
 86 int main()
 87 {
 88     int st,ed;
 89     while(~scanf("%d%d",&m,&n)) {
 90         memset(head,-1,sizeof(head));
 91         cnt=-1;
 92         for(reint i=1;i<=m;i++) {
 93             int a,b,c;
 94             read(a),read(b),read(c);
 95             add(a,b,c);
 96             add(b,a,0);
 97         }
 98         write(Dinic(1,n)),pn;
 99     }
100     return 0;
101 }