题目描述

在农夫约翰的农场上，每逢下雨，贝茜最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。
农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。
根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。

思路

第一个网络流
用ff算法，算简单的了
也不好解释什么

#include <stdio.h>
#define min(x,y) x<y?x:y
#define maxn 200
int n,m,s,t,ans=0;
int c[maxn][maxn],b[maxn];
int find(int k)
{
    if (k==t) return true;
    for (int i=1;i<=n;i++)
        if (b[i]==-1&&c[k][i]>0)
        {
            b[i]=k;
            if (find(i)) return true;
        } 
    return false;
}
int add()
{
    int d=0x7fffffff;
    int i=t;
    while (b[i]!=0)
    {
        if (c[b[i]][i]>0) d=min(d,c[b[i]][i]);
        i=b[i];
    }
    i=t;
    while (b[i]!=0)
    {
        c[b[i]][i]-=d;
        c[i][b[i]]+=d;
        i=b[i];
    }
    ans+=d;
}
int main()
{
    scanf("%d%d",&m,&n);
    s=1,t=n;
    for (int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        c[x][y]+=z;
    }
    for (int i=1;i<=n;i++)
        b[i]=-1;
    b[s]=0;
    while (find(s))
    {
        add();
        for (int i=1;i<=n;i++) 
            b[i]=-1;
        b[s]=0;
    }
    printf("%d\n",ans);
}

Dinic

#include <stdio.h>
#include <string.h>
#include <queue>
#define maxn 4000
#define min(x,y) x<y?x:y
#define INF 0x7f7f7f7f
#define fill(x,i) memset(x,i,sizeof(x))
using namespace std;
struct edge{int y,w,rev,next;}e[maxn];
int ls[maxn],n,m,maxE=0,S,E,state[maxn];
bool vis[maxn];
int add(int x,int y,int w)
{
    e[++maxE]=(edge){y,w,maxE+1,ls[x]};
    ls[x]=maxE;
    e[++maxE]=(edge){x,0,maxE-1,ls[y]};
    ls[y]=maxE;
}
int bfs(int x)
{
    queue <int> t;
    t.push(x);
    fill(state,63);
    state[x]=0;
    while (!t.empty())
    {
        int tt=t.front();t.pop();
        for (int i=ls[tt];i;i=e[i].next)
        {
            if (e[i].w>0&&state[tt]+1<state[e[i].y])
            {
                state[e[i].y]=state[tt]+1;
                t.push(e[i].y);
                if (e[i].y==E)
                    return true;
            }
        }
    }
    return false;
}
int find(int x,int mn)
{
    if (x==E) return mn;
    for (int i=ls[x];i;i=e[i].next)
        if (state[x]+1==state[e[i].y]&&e[i].w>0)
        {
            int d=find(e[i].y,min(mn,e[i].w));
            if (d>0)
            {
                e[i].w-=d;
                e[e[i].rev].w+=d;
                return d;
            }
        }
    return 0;
}
int main()
{
    scanf("%d%d",&m,&n);
    S=1; E=n;
    for (int i=1;i<=m;i++)
    {
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        add(x,y,w);
    }
    int ans=0;
    while (bfs(S))
    {
        ans+=find(S,INF);
    }
    printf("%d\n",ans);
}