记录编号 |
217703 |
评测结果 |
AAAAAAAAAAAA |
题目名称 |
草地排水 |
最终得分 |
100 |
用户昵称 |
stone |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.003 s |
提交时间 |
2016-01-05 20:41:11 |
内存使用 |
1.12 MiB |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
struct Dinic{
static const int maxn = 200 + 5;
static const int maxm = maxn * maxn;
static const int oo = 0x3f3f3f3f;
int n,m,s,t;
int tot;
int first[maxn],next[maxm];
int u[maxm],v[maxm],cap[maxm],flow[maxm];
int cur[maxn],dis[maxn];
bool vi[maxn];
Dinic(){tot=0;memset(first,-1,sizeof first);}
void Clear(){tot = 0;memset(first,-1,sizeof first);}
void Add(int from,int to,int cp){
u[tot] = from;v[tot] = to;cap[tot] = cp;flow[tot] = 0;
next[tot] = first[u[tot]];
first[u[tot]] = tot;
++ tot;
}
bool bfs(){
memset(vi,false,sizeof vi);
queue <int> q;
dis[s] = 0;vi[s] = true;
q.push(s);
while(!q.empty()){
int now = q.front();q.pop();
for(int i = first[now];i != -1;i = next[i]){
if(!vi[v[i]] && cap[i] > flow[i]){
vi[v[i]] = true;
dis[v[i]] = dis[now] + 1;
q.push(v[i]);
}
}
}
return vi[t];
}
int dfs(int x,int a){
if(x == t || a == 0) return a;
int flw=0,f;
int &i = cur[x];
for(i = first[x];i != -1;i = next[i]){
if(dis[x] + 1 == dis[v[i]] && (f = dfs(v[i],min(a,cap[i]-flow[i]))) > 0){
flow[i] += f;flow[i^1] -= f;
a -= f;flw += f;
if(a == 0) break;
}
}
return flw;
}
int Maxflow(int s,int t){
this->s = s;this->t = t;
int flw=0;
while(bfs()){
memset(cur,0,sizeof cur);
flw += dfs(s,oo);
}
return flw;
}
}Net;
int main(){
#ifndef ONLINE_JUDGE
freopen("ditch.in","r",stdin);
freopen("ditch.out","w",stdout);
#endif
int x,y,z;
scanf("%d%d",&Net.m,&Net.n);
for(int i = 1;i <= Net.m;++ i){
scanf("%d%d%d",&x,&y,&z);
Net.Add(x,y,z);
Net.Add(y,x,0);
}
printf("%d\n",Net.Maxflow(1,Net.n));
#ifndef ONLINE_JUDGE
fclose(stdin);fclose(stdout);
#endif
return 0;
}