题意:现在有m个池塘(从1到m开始编号,1为源点,m为汇点),及n条水渠,给出这n条水渠所连接的池塘和所能流过的水量,求水渠中所能流过的水的最大容量.

求1到n的最大流，套模板。。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 using namespace std; 7 #define inf 0x7fffffff 8 #define N 205 9 #define M 40510 int cur[N],pre[N],gap[N],dis[N];11 int size,head[N];12 struct Edge13 {14     int v,w,next;15     Edge(){}16     Edge(int V,int W,int NEXT):v(V),w(W),next(NEXT){}17 }edge[M];18 void Init()19 {20     memset(head,-1,sizeof(head));21     size = 0;22 }23 void InsertEdge(int u,int v,int w)24 {25     edge[size] = Edge(v,w,head[u]);26     head[u] = size++;27     edge[size] = Edge(u,0,head[v]);28     head[v] = size++;29 }30 int Isap(int st,int ed,int n)31 {32     for(int i=0; i<=n; i++)33     {34         dis[i] = gap[i] = 0;35         cur[i] = head[i];36     }37     int u = pre[st] = st;38     int aug = inf , maxflow = 0;39     while(dis[st] < n)40     {41         loop:42         for(int &i=cur[u]; i!=-1; i=edge[i].next)43         {44             int v = edge[i].v;45             if(edge[i].w && dis[u] == dis[v] + 1)46             {47                 aug = min(aug,edge[i].w);48                 pre[v] = u;49                 u = v;50                 if(v==ed)51                 {52                     maxflow += aug;53                     for(u=pre[u]; v!=st; v=u,u=pre[u])54                     {55                         edge[cur[u]].w -= aug;56                         edge[cur[u]^1].w += aug;57                     }58                     aug = inf;59                 }60                 goto loop;61             }62         }63         int mindis = n;64         for(int i=head[u]; i!=-1; i=edge[i].next)65         {66             int v =edge[i].v;67             if(edge[i].w && dis[v]