芝生排水(ネットワーク流)gzoi
広州の学生はここを見ています.
http://www.gdgzoi.com/JudgeOnline/problem.php?cid=1045&pid=0
Description
農夫のジョンの畑に雨が降るたびに、Bessieの大好きなクローバーの中に池が形成され、クローバーがしばらく水に覆われ、成長するのに長い時間がかかります.そのため、農夫のジョンは排水の溝を作って、Bessieの三葉草地がずっと水に覆われず、最近の渓流に水を排出しなければならない.エンジニアとして、農夫のジョンは排水溝の始端に調節器を設置したので、溝に入る水流速度を制御することができます.
農夫Johnは、各溝が毎分何ガロンの水を輸送できるかを知っているだけでなく、溝の正確な配置を知っていて、池から水を排出し、複雑なネットワークを通じて各溝と渓流に注入しています.
池から流れ出て渓流に流入できる水の最大速度を決定するすべての関連情報を与えた.各溝に対して、水流の方向は唯一であるが、水は循環して流れることができる.
入力
入力には、いくつかのテスト・インスタンスが含まれます.各試験例について、第1行は、スペースで区切られた2つの整数N(0<=N<=200)およびM(2<=M<=200)を与え、Nは農夫Johnが掘った溝の数であり、Mはこれらの溝の交差点の数である.交差点1は池で、交差点Mは渓流です.後のN行は1行当たり3つの整数を与えた:Si,EiおよびCi,SiおよびEi(1<=Si,Ei<=M)は,水がSiからEiへ流れる溝の2つの交差点を示した.Ci(0<=Ci<=1億円)はこの溝を通る水流の最大流量である.
しゅつりょく
各試験例について、池から排水する最大流量の整数を出力する.
サンプル入力
サンプル出力
5 4 1 2 40 1 4 20 2 4 20 2 3 30 3 4 10
50
このテーマは遊びです.
ダイレクトコード
ネットの流れの自分で独学を学ぶのもとても简単で、ここは多く话しません.....
http://www.gdgzoi.com/JudgeOnline/problem.php?cid=1045&pid=0
Description
農夫のジョンの畑に雨が降るたびに、Bessieの大好きなクローバーの中に池が形成され、クローバーがしばらく水に覆われ、成長するのに長い時間がかかります.そのため、農夫のジョンは排水の溝を作って、Bessieの三葉草地がずっと水に覆われず、最近の渓流に水を排出しなければならない.エンジニアとして、農夫のジョンは排水溝の始端に調節器を設置したので、溝に入る水流速度を制御することができます.
農夫Johnは、各溝が毎分何ガロンの水を輸送できるかを知っているだけでなく、溝の正確な配置を知っていて、池から水を排出し、複雑なネットワークを通じて各溝と渓流に注入しています.
池から流れ出て渓流に流入できる水の最大速度を決定するすべての関連情報を与えた.各溝に対して、水流の方向は唯一であるが、水は循環して流れることができる.
入力
入力には、いくつかのテスト・インスタンスが含まれます.各試験例について、第1行は、スペースで区切られた2つの整数N(0<=N<=200)およびM(2<=M<=200)を与え、Nは農夫Johnが掘った溝の数であり、Mはこれらの溝の交差点の数である.交差点1は池で、交差点Mは渓流です.後のN行は1行当たり3つの整数を与えた:Si,EiおよびCi,SiおよびEi(1<=Si,Ei<=M)は,水がSiからEiへ流れる溝の2つの交差点を示した.Ci(0<=Ci<=1億円)はこの溝を通る水流の最大流量である.
しゅつりょく
各試験例について、池から排水する最大流量の整数を出力する.
サンプル入力
サンプル出力
5 4 1 2 40 1 4 20 2 4 20 2 3 30 3 4 10
50
このテーマは遊びです.
ダイレクトコード
#include
#include
#include
#include
#include
#include
#define maxn 205
#define INF 10000005
using namespace std;
struct Edge{
int from,to,cap,flow;
Edge(int u,int v,int c,int f) :from(u),to(v),cap(c),flow(f) {}
};
vector edges;
vector G[maxn];
int a[maxn];
int p[maxn];
int n,m;
/*void init(int n) {
for(int i=0;i Q;
Q.push(s);
a[s]=INF;
while(!Q.empty()) {
int x=Q.front(); Q.pop();
for(unsigned int i=0;ie.flow){
p[e.to]=G[x][i];
a[e.to]=min(a[x],e.cap-e.flow);
Q.push(e.to);
}
}
if(a[t]) break;
}
if(!a[t]) break;
for(int u=t;u!=s;u=edges[p[u]].from) {
edges[p[u]].flow+=a[t];
edges[p[u]^1].flow-=a[t];
}
flow+=a[t];
}
return flow;
}
int main()
{std::ios::sync_with_stdio(false);
int from,to,c;
cin>>n>>m;
for(int i=0;i>from>>to>>c;
AddEdge(from,to,c);
}
cout<
ネットの流れの自分で独学を学ぶのもとても简単で、ここは多く话しません.....