首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >P2740 [USACO4.2]草地排水Drainage Ditches

P2740 [USACO4.2]草地排水Drainage Ditches

作者头像
attack
发布2018-04-12 14:13:51
5510
发布2018-04-12 14:13:51
举报

题目背景

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

题目描述

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

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

输入输出格式

输入格式:

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

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

输出格式:

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

输入输出样例

输入样例#1:

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

输出样例#1:

50

说明

题目翻译来自NOCOW。

USACO Training Section 4.2

裸地最大流问题,Dinic算法

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<queue>
  6 #include<algorithm>
  7 #define lli long long int 
  8 using namespace std;
  9 const int MAXN=300001;
 10 const int maxn=0x7fffff;
 11 void read(int &n)
 12 {
 13     char c='+';int x=0;bool flag=0;
 14     while(c<'0'||c>'9')
 15     {c=getchar();if(c=='-')flag=1;}
 16     while(c>='0'&&c<='9')
 17     {x=x*10+c-48;c=getchar();}
 18     flag==1?n=-x:n=x;
 19 }
 20 struct node
 21 {
 22     int u,v,flow,cap,nxt;
 23 }edge[MAXN];
 24 int head[MAXN];
 25 int num=0;
 26 int n,m,S,T;
 27 int dis[MAXN];
 28 int vis[MAXN];
 29 int cur[MAXN];
 30 void add_edge(int x,int y,int z)
 31 {
 32     edge[num].u=x;
 33     edge[num].v=y;
 34     edge[num].cap=z;
 35     edge[num].flow=0;
 36     edge[num].nxt=head[x];
 37     head[x]=num++;
 38 }
 39 bool bfs(int bg,int ed)
 40 {
 41     memset(dis,-1,sizeof(dis));
 42     queue<int>q;
 43     q.push(bg);
 44     dis[bg]=0;
 45     while(!q.empty())
 46     {
 47         int p=q.front();
 48         q.pop();
 49         for(int i=head[p];i!=-1;i=edge[i].nxt)
 50         {
 51             if(dis[edge[i].v]==-1&&edge[i].cap>edge[i].flow)
 52             {
 53                 vis[edge[i].v]=1;
 54                 dis[edge[i].v]=dis[edge[i].u]+1;
 55                   q.push(edge[i].v);            
 56             }
 57         }
 58     }
 59     if(dis[ed]==-1)
 60         return 0;
 61     else return 1;
 62 }
 63 int dfs(int now,int a)// a:所有弧的最小残量 
 64 {
 65     if(now==T||a<=0)
 66         return a;
 67         
 68     int flow=0,f;
 69     for(int i=head[now];i!=-1;i=edge[i].nxt)
 70     {
 71         if(dis[now]+1==dis[edge[i].v]&&edge[i].cap-edge[i].flow>0)
 72         {
 73             f=dfs(edge[i].v,min(a,edge[i].cap-edge[i].flow));
 74             edge[i].flow+=f;
 75             edge[i^1].flow-=f;
 76             flow+=f;
 77             a-=f;
 78             if(a<=0)break;
 79         }
 80     }
 81     return flow;
 82 }
 83 void Dinic(int S,int T)
 84 {
 85     int ansflow=0;
 86     for(int i=1;i<=n;i++)
 87             cur[i]=head[i];
 88     while(bfs(S,T))// 求出层级
 89         ansflow+=dfs(S,maxn); 
 90     printf("%d",ansflow);
 91     
 92 }
 93 int main()
 94 {
 95     read(m);read(n);
 96 //    swap(n,m);
 97     S=1;T=n;
 98    // read(S);read(T);
 99     for(int i=1;i<=n;i++)
100         head[i]=-1;
101     for(int i=1;i<=m;i++)
102     {
103         int x,y,z;
104         read(x);read(y);read(z);
105         add_edge(x,y,z);
106         add_edge(y,x,0);
107     }
108     Dinic(S,T);
109     return 0;
110 }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-07-10 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目背景
  • 题目描述
  • 输入输出格式
  • 输入输出样例
  • 说明
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档