题目描述

约翰总希望他的奶牛有足够的水喝，因此他找来了农场的水管地图，想算算牛棚得到的水的 总流量.农场里一共有N根水管.约翰发现水管网络混乱不堪，他试图对其进行简 化.他简化的方式是这样的：
两根水管串联，则可以用较小流量的那根水管代替总流量.
两根水管并联，则可以用流量为两根水管流量和的一根水管代替它们
当然，如果存在一根水管一端什么也没有连接，可以将它移除.
请写个程序算出从水井A到牛棚Z的总流量.数据保证所有输入的水管网络都可以用上述方法 简化.

思路

将题目读懂就是让我们求最大流
将每一个点都连双向边，源点为”A”汇点为”Z”
把每一个字母都化为ascall码的数字
用dinic跑一边最大流就可以了
事实证明裸的dinic会超时，一定要加当前弧优化
这里就不赘述算法了，提供一个思路

#include 
#include 
#include 
#include 
#define maxn 400000
#define min(x,y) x'9'){if (ch=='-')p=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*p;
}
int add(int x,int y,int w)
{
    e[++maxE]=(edge){y,w,ls[x]};
    ls[x]=maxE;
    e[++maxE]=(edge){x,0,ls[y]};
    ls[y]=maxE;
}
int bfs(int x)
{
    queue  t;
    t.push(x);
    fill(state,0);
    state[x]=1;
    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[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 cur[maxn];
int find(int x,int mn)
{
    if (x==E||!mn) return mn;
    int ret=0;
    for (int &i=cur[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-ret,e[i].w));
            e[i].w-=d;
            e[i^1].w+=d;
            ret+=d;
            if (ret==mn) break;
        }
    return ret;
}
int main()
{
    int n=read();
    S='A';E='Z';
    for (int i=1;i<=n;i++)
    {
        char aa[100],bb[100];
        int x;
        scanf("%s%s%d",aa,bb,&x);
        int a=aa[0],b=bb[0];
        add(a,b,x);
        add(b,a,x);
    }
    int ans=0;
    while (bfs(S))
    {
        for (int i=0;i<=E+maxE;i++) 
            cur[i]=ls[i];
        ans+=find(S,INF);
    }
    printf("%d\n",ans);
}