P3376 【模板】網路最大流（70）

題目描述

如題，給出一個網路圖，以及其源點和匯點，求出其網路最大流。

輸入輸出格式

輸入格式：

第一行包含四個正整數N、M、S、T，分別表示點的個數、有向邊的個數、源點序號、匯點序號。

接下來M行每行包含三個正整數ui、vi、wi，表示第i條有向邊從ui出發，到達vi，邊權為wi（即該邊最大流量為wi）

輸出格式：

一行，包含一個正整數，即為該網路的最大流。

輸入輸出樣例

4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40

50

說明

時空限制：1000ms,128M

數據規模：

對於30%的數據：N<=10，M<=25

對於70%的數據：N<=200，M<=1000

對於100%的數據：N<=10000，M<=100000

樣例說明：

題目中存在3條路徑：

4-->2-->3，該路線可通過20的流量

4-->3，可通過20的流量

4-->2-->1-->3，可通過10的流量（邊4-->2之前已經耗費了20的流量）

故流量總計20+20+10=50。輸出50。

莫名其妙WA三個點，

改天再調

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<queue>
  6 #include<algorithm>
  7 #define lli long long int 
  8 using namespace std;
  9 const int MAXN=300001;
 10 const int maxn=0x7ffffff;
 11 void read(int &n)
 12 {
 13     char c='+';int x=0;bool flag=0;
 14     while(c<'0'||c>'9')
 15     {c=getchar();if(c=='-')flag=1;}
 16     while(c>='0'&&c<='9')
 17     {x=x*10+c-48;c=getchar();}
 18     flag==1?n=-x:n=x;
 19 }
 20 struct node
 21 {
 22     int u,v,flow,cap,nxt;
 23 }edge[MAXN];
 24 int head[MAXN];
 25 int num=1;
 26 int n,m,S,T;
 27 int dis[MAXN];
 28 int vis[MAXN];
 29 int cur[MAXN];
 30 void add_edge(int x,int y,int z)
 31 {
 32     edge[num].u=x;
 33     edge[num].v=y;
 34     edge[num].cap=z;
 35     edge[num].flow=0;
 36     edge[num].nxt=head[x];
 37     head[x]=num++;
 38 }
 39 bool bfs(int bg,int ed)
 40 {
 41     memset(vis,0,sizeof(vis));
 42     memset(dis,0,sizeof(dis));
 43     queue<int>q;
 44     q.push(bg);
 45     dis[bg]=1;
 46     vis[bg]=1;
 47     while(!q.empty())
 48     {
 49         int p=q.front();
 50         q.pop();
 51         for(int i=head[p];i!=-1;i=edge[i].nxt)
 52         {
 53             if(!vis[edge[i].v]&&edge[i].cap-edge[i].flow>0)
 54             {
 55                 vis[edge[i].v]=1;
 56                 dis[edge[i].v]=dis[edge[i].u]+1;
 57                   q.push(edge[i].v);            
 58             }
 59         }
 60     }
 61     return vis[ed];
 62 }
 63 int dfs(int now,int a)// a:所有弧的最小殘量 
 64 {
 65     if(now==T||a<=0)
 66         return a;
 67     int flow=0,f;
 68     for(int i=head[now];i!=-1;i=edge[i].nxt)
 69     {
 70         if(dis[now]+1==dis[edge[i].v]&&edge[i].cap-edge[i].flow>0)
 71         {
 72             f=dfs(edge[i].v,min(a,edge[i].cap-edge[i].flow));
 73             edge[i].flow+=f;
 74             edge[i^1].flow-=f;
 75             flow+=f;
 76             a-=f;
 77             if(a<=0)break;
 78         }
 79     }
 80     return flow;
 81 }
 82 void Dinic(int S,int T)
 83 {
 84     int ansflow=0;
 85     //for(int i=1;i<=n;i++)
 86     //        cur[i]=head[i];
 87     while(bfs(S,T))
 88     {
 89         ansflow+=dfs(S,maxn);
 90     }// 求出層級 
 91     printf("%d",ansflow);
 92     
 93 }
 94 int main()
 95 {
 96     read(n);read(m);
 97 //    swap(n,m);
 98 //    S=1;T=m;
 99     read(S);read(T);
100     for(int i=1;i<=n;i++)
101         head[i]=-1;
102     for(int i=1;i<=m;i++)
103     {
104         int x,y,z;
105         read(x);read(y);read(z);
106         add_edge(x,y,z);
107         add_edge(y,x,0);
108     }
109     Dinic(S,T);
110     return 0;
111 }