1 #include<cmath> 2 #include<cstdio> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 const int MAXN=200+10,inf=2000000000; 8 int c[MAXN][MAXN],f[MAXN][MAXN],q[MAXN][2],n,m,ans;//c数组是记录容量，f数组是记录流量，q为队列，因为既要记录当前点，也要记录路径，所以开2维 9 bool p[MAXN],mark=true;//p代表每个点是否可取（每个点只能取一次）10 inline void read(int &x)11 {12     x=0;13     char c=getchar();14     while(c<‘0‘||c>‘9‘)c=getchar();15     while(c>=‘0‘&&c<=‘9‘)16     {17         x=(x<<3)+(x<<1)+(c^‘0‘);18         c=getchar();19     }20 }21 int main()22 {23     read(m);read(n);24     for(register int i=1;i<=m;++i)//输入容量，没有连通的容量就为025     {26         int x,y,z;27         read(x);read(y);read(z);28         c[x][y]+=z;//有可能两个点之间有多条管道29     }30     while(mark)31     {32         mark=false;33         for(register int i=1;i<=n;++i)p[i]=true;//把每个点都设为可取34         p[1]=false;//把1取走35         q[1][0]=1;//放入队列36         q[1][1]=0;//1的前面路径为037         int head=0,tail=1;//队列的头和尾38         while(head<tail)//走第一遍，寻找起点到终点的路径39         {40             head++;41             int x=q[head][0];//取出队首元素42             for(register int i=1;i<=n;++i)43             {44                 if(p[i]&&(c[x][i]>f[x][i]||f[i][x]>0))//判断如果该点可取并且容量大于流量（因为f初始化为0，而不连通的两点c数组的值也为0，所以不会计入）或当前方向为反向时（反向没有容量）判断正向是否有流量，若有流量则代表有容量45                 {46                     p[i]=false;//设为不可取47                     q[++tail][0]=i;//放入队列48                     q[tail][1]=head;//记录路径（注意：存的是head，即当前点在队列中的位置）49                     if(i==n)//如果当前点是终点，那么已经找到了一条路径50                     {51                         mark=true;52                         break;//直接跳出循环53                     }54                 }55             }56             if(mark)break;57         }58         if(!mark)break;//如果找不到路径了，就是都搜完了，就跳出循环59         int minn=inf,pos=tail;//minn代表瓶颈，pos从终点向前找60         while(q[pos][1])//走第二遍，从后往前寻找瓶颈  //只要当前点的前面还有点61         {62             int x=q[q[pos][1]][0],y=q[pos][0];//x，y为一条管道的两个端点，x为前面的点，y为后面的点63             if(c[x][y]>f[x][y])minn=min(minn,c[x][y]-f[x][y]);//如果容量大于流量，即还可以流，那么更新瓶颈64             else if(f[y][x]>0)minn=min(minn,f[y][x]);//另一种情况，反向流量最大为正向流量65             pos=q[pos][1];//进行下一个点的搜索66         }67         pos=tail;68         while(q[pos][1])//走第三遍，更改路径上的流量69         {70             int x=q[q[pos][1]][0],y=q[pos][0];71             if(c[x][y]>f[x][y])f[x][y]+=minn;//正向，（正向）流量加上瓶颈72             else f[y][x]-=minn;//反向，（正向）流量减去瓶颈73             pos=q[pos][1];74         }75     }76     for(register int i=2;i<=n;++i)ans+=f[1][i];//从起点流出的必会流到终点，起点（或终点）的所有流量即为最大流77     printf("%d",ans);78     return 0;79 }