题意:n个池塘，m条水渠，求从第一个池塘到第m个池塘能运送的最大流量；

思路：裸最大流dicnic算法。建分层图并不断找增广路，直到找不到增广路即为最大流。

邻接表实现：

#include 
     
      #include 
      
       #include 
       
        using namespace std;#define MAXN 210#define INF 0x3f3f3f3fstruct Edge{    int st, ed;    int c;    int next;}edge[MAXN << 1];int n, m;int s, t;int ans;int e = 0; int head[MAXN];int d[MAXN];int min(int a, int b){    return a < b ? a : b;}void init(){    int i, j;    int a, b, c;     s = 1;   //源点    t = m;   //汇点    e = 0;   //边数    ans = 0;    memset(head, -1, sizeof(head));    for(i = 1; i <= n; i++)    {        scanf("%d%d%d", &a, &b, &c);        edge[e].st = a;        edge[e].ed = b;        edge[e].c = c;        edge[e].next = head[a];        head[a]= e++;        edge[e].st = b;        edge[e].ed = a;        edge[e].next = head[b];        head[b] = e++;    }}int bfs(){    memset(d, -1, sizeof(d));    queue
        
          q;    d[s] = 0;    q.push(s);    int i;    int cur;    while(!q.empty())    {        cur = q.front();        q.pop();        for(i = head[cur]; i != -1; i = edge[i].next)        {            if(d[edge[i].ed] == -1 && edge[i].c > 0)            {                d[edge[i].ed] = d[cur] + 1;                 q.push(edge[i].ed);            }            }    }    if(d[t] < 0)        return 0;    return 1;}int dinic(int x, int flow){    if(x == t)        return flow;    int i, a;    for(i = head[x]; i != -1; i = edge[i].next)    {        if(d[edge[i].ed] == d[x] + 1 && edge[i].c > 0 && (a = dinic(edge[i].ed, min(flow, edge[i].c))))        {            edge[i].c -= a;            edge[i ^ 1].c += a;            return a;            }    }    return 0;}void solve(){    while(scanf("%d%d", &n, &m) != EOF)    {        init();        while(bfs()) //建图，增广        {            int increment;            increment = dinic(1, INF);                ans +=  increment;         }        printf("%d\n", ans);    }}int main(){    solve();    return 0;}
        
       
      
     

邻接矩阵实现：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define min(x,y) ((x
         
          0)               {                  dis[i]=dis[j]+1;                  q[++r]=i;               }     }     if (dis[N]>0)        return 1;     else        return 0;//汇点的DIS小于零,表明BFS不到汇点}//Find代表一次增广,函数返回本次增广的流量,返回0表示无法增广int find(int x,int low)//Low是源点到现在最窄的(剩余流量最小)的边的剩余流量{    int i,a=0;    if (x==N)return low;//是汇点    for (i=1;i<=N;i++)    if (tab[x][i] >0 //联通     && dis[i]==dis[x]+1 //是分层图的下一层     &&(a=find(i,min(low,tab[x][i]))))//能到汇点(a !=  0)    {       tab[x][i]-=a;       tab[i][x]+=a;       return a;    }    return 0;}int main(){    //freopen("ditch.in" ,"r",stdin );    //freopen("ditch.out","w",stdout);    int i,j,f,t,flow,tans;    while (scanf("%d%d",&M,&N)!=EOF){    memset(tab,0,sizeof(tab));    for (i=1;i<=M;i++)    {        scanf("%d%d%d",&f,&t,&flow);        tab[f][t]+=flow;    }    //    ANS=0;    while (BFS())//要不停地建立分层图,如果BFS不到汇点才结束    {          while(tans=find(1,0x7fffffff))ANS+=tans;//一次BFS要不停地找增广路,直到找不到为止    }    printf("%d\n",ANS);    }}
         
        
       
      
     

 sap算法：（出现断链时直接退出；对当前弧优化）

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define MAXN 500#define MAXE 40000#define INF 0x7ffffffflong ne,nv,tmp,s,t,index;struct Edge{    long next,pair;    long v,cap,flow;}edge[MAXE];long net[MAXN];long ISAP(){    long numb[MAXN],dist[MAXN],curedge[MAXN],pre[MAXN];    long cur_flow,max_flow,u,tmp,neck,i;    memset(dist,0,sizeof(dist));    memset(numb,0,sizeof(numb));    memset(pre,-1,sizeof(pre));    for(i = 1 ; i <= nv ; ++i)        curedge[i] = net[i];    numb[nv] = nv;    max_flow = 0;    u = s;    while(dist[s] < nv)    {        /* first , check if has augmemt flow */        if(u == t)        {            cur_flow = INF;            for(i = s; i != t;i = edge[curedge[i]].v)             {                  if(cur_flow > edge[curedge[i]].cap)                {                    neck = i;                    cur_flow = edge[curedge[i]].cap;                }            }            for(i = s; i != t; i = edge[curedge[i]].v)            {                tmp = curedge[i];                edge[tmp].cap -= cur_flow;                edge[tmp].flow += cur_flow;                tmp = edge[tmp].pair;                edge[tmp].cap += cur_flow;                edge[tmp].flow -= cur_flow;            }            max_flow += cur_flow;            u = neck;        }        /* if .... else ... */        for(i = curedge[u]; i != -1; i = edge[i].next)            if(edge[i].cap > 0 && dist[u] == dist[edge[i].v]+1)                break;        if(i != -1)        {            curedge[u] = i;            pre[edge[i].v] = u;            u = edge[i].v;        }else{            if(0 == --numb[dist[u]]) break;            curedge[u] = net[u];            for(tmp = nv,i = net[u]; i != -1; i = edge[i].next)                if(edge[i].cap > 0)                    tmp = tmp