poj1273 草地排水 [最大流]

in 题目 with 0 comment

Description

在农夫约翰的农场上,每逢下雨,贝茜最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了,并且小草要继续生长还要花相当长一段时间。因此,农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼(不用担心,雨水会流向附近的一条小溪)。作为一名一流的技师,农夫约翰已经在每条排水沟的一端安上了控制器,这样他可以控制流入排水沟的水流量。

农夫约翰知道每一条排水沟每分钟可以流过的水量,和排水系统的准确布局(起点为水潭而终点为小溪的一张网)。需要注意的是,有些时候从一处到另一处不只有一条排水沟。

根据这些信息,计算从水潭排水到小溪的最大流量。对于给出的每条排水沟,雨水只能沿着一个方向流动,注意可能会出现雨水环形流动的情形。


input

第1行: 两个用空格分开的整数N $ ( 0 \le N \le 200 ) $ 和 M $ (2 \le M \le 200) $。N是农夫John已经挖好的排水沟的数量,M是排水沟交叉点的数量。交点1是水潭,交点M是小溪。

第2行到第N+1行: 每行有三个整数,Si, Ei, 和 Ci。Si 和 Ei $ (1 \le Si, Ei \le M) $ 指明排水沟两端的交点,雨水从Si 流向Ei。Ci $ (0 \le Ci \le 10,000,000) $是这条排水沟的最大容量。


Output

输出一个整数,即排水的最大流量。


Sample Input

5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10


Sample Output

50


Sourse

题目翻译来自NOCOW.
USACO Training Section 4.2
题目来自洛谷.


Solution

直接建图,最大流模板题(dinic)


Code

#include<bits/stdc++.h>
#define maxn 220
#define maxe 50010
#define INF 0x7f7f7f7f
//#define COGS
using namespace std;
int n,m,cnt=1;
int head[maxn],dis[maxn];

struct edge
{
    int to,next,val;
}e[maxe];

inline int read()
{
    char ch;
    int read=0,sign=1;
    do
        ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-');
    if(ch=='-') sign=-1,ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        read=read*10+ch-'0';
        ch=getchar();
    }
    return sign*read;
}

inline void ins(int u,int v,int w)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].val=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}

inline void insert(int u,int v,int w)
{ ins(u,v,w),ins(v,u,0); }

bool bfs()
{
    memset(dis,-1,sizeof(dis));
    queue<int> q;
    q.push(1);
    dis[1]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        int i=head[u];
        while(i)
        {
            if(e[i].val && dis[e[i].to]==-1)
                q.push(e[i].to),dis[e[i].to]=dis[u]+1;
            i=e[i].next;
        }
    }
    if(dis[n]==-1) return 0;
    return 1;
}

int dfs(int x,int flow)
{
    if(x==n) return flow;
    int i=head[x],used=0,w;
    while(i)
    {
        if(e[i].val && dis[e[i].to]==dis[x]+1)
        {
            w=flow-used;
            w=dfs(e[i].to,min(w,e[i].val));
            e[i].val-=w;
            e[i^1].val+=w;
            used+=w;
            if(used==flow) return flow;
        }
        i=e[i].next;
    }
    if(!used) dis[x]=-1;
    return used;
}

int dinic()
{
    int ans=0;
    while(bfs()) ans+=dfs(1,INF);
    return ans;
}

int main()
{
#ifdef COGS
    freopen("ditch.in","r",stdin);
    freopen("ditch.out","w",stdout);
#endif
    m=read(),n=read();
    for(int i=1;i<=m;++i)
    {
        int u=read();
        int v=read();
        int w=read();
        insert(u,v,w);
    }
    printf("%d\n",dinic());
    return 0;
} 

/*
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
*/

扫描二维码,在手机上阅读!
Responses