首页 > 代码库 > codevs 1993 草地排水 USACO
codevs 1993 草地排水 USACO
时间限制: 2 s
空间限制: 256000 KB
题目等级 : 钻石 Diamond
题目描述 Description
在农夫约翰的农场上，每逢下雨，Bessie最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。
农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。
根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。
输入描述 Input Description
第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)是这条排水沟的最大容量。
输出描述 Output Description
输出一个整数，即排水的最大流量。
样例输入 Sample Input
5 41 2 401 4 202 4 202 3 303 4 10
样例输出 Sample Output
50
初学网络流
屠龙宝刀点击就送
#include <cstring>#include <cstdio>#include <vector>#include <queue>#define inf 0x7fffffffusing namespace std;vector<int>vec;bool vis[205];int n,m,i,j,Answer,dis[205],atlas[205][205];bool bfs(){ queue<int>q; memset(dis,-1,n*n*4); q.push(1);dis[1]=0; while(!q.empty() ) { int tope=q.front() ; q.pop() ; for(i=1;i<=m;++i) { if(atlas[tope][i]>0&&dis[i]==-1) { dis[i]=dis[tope]+1; if(i==m) return 1; else q.push(i); } } } return 0;}void network(){ memset(vis,0,sizeof(vis));vis[1]=1; vec.push_back(1); while(!vec.empty() ) { int tope=vec.back(); if(tope==m) { int v,minx=inf; for(i=1;i<vec.size() ;++i) { if(atlas[vec[i-1]][vec[i]]>0&&atlas[vec[i-1]][vec[i]]<minx) { v=vec[i-1]; minx=atlas[vec[i-1]][vec[i]]; } } Answer+=minx; for(i=1;i<vec.size() ;++i) { atlas[vec[i-1]][vec[i]]-=minx; atlas[vec[i]][vec[i-1]]+=minx; } while(!vec.empty() &&vec.back() !=v) { vis[vec.back() ]=0; vec.pop_back() ; } } else { int i=1; for(i=1;i<=m;++i) { if(atlas[tope][i]>0&&!vis[i]&&dis[tope]+1==dis[i]) { vis[i]=1; vec.push_back(i); break; } } if(i>m) vec.pop_back(); } }}int main(){ scanf("%d%d",&n,&m); int u,v,l; for(i=0;i<n;++i) { scanf("%d%d%d",&u,&v,&l); atlas[u][v]+=l; } while(bfs()) network(); printf("%d",Answer); return 0;}
codevs 1993 草地排水 USACO
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。