记录编号 |
430270 |
评测结果 |
AAAAAAAAAAAA |
题目名称 |
草地排水 |
最终得分 |
100 |
用户昵称 |
Hallmeow |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.009 s |
提交时间 |
2017-07-29 16:19:26 |
内存使用 |
1.08 MiB |
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
#define LL long long
#define pos(i,a,b) for(LL i=(a);i<=(b);i++)
#define N 40100
const int inf=0x7fffffff;
struct haha{
int next,to,w;
}edge[N];
int head[N],cnt;
int n,m;
void add(int u,int v,int w){
edge[cnt].w=w;
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
int dep[N];
bool bfs(){
memset(dep,0,sizeof(dep));
queue<int> q;
q.push(1);
dep[1]=1;
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=head[now];i!=-1;i=edge[i].next){
int to=edge[i].to,w=edge[i].w;
if(w&&(!dep[to])){
dep[to]=dep[now]+1;
q.push(to);
if(to==n){
return 1;
}
}
}
}
return 0;
}
int dfs(int now,int f){
if(now==n){
return f;
}
int tmp=f;
for(int i=head[now];i!=-1;i=edge[i].next){
int to=edge[i].to,w=edge[i].w;
if(w&&tmp&&dep[to]==dep[now]+1){
int k=dfs(to,min(tmp,w));
if(!k){
dep[to]=0;
continue;
}
edge[i].w-=k;
edge[i^1].w+=k;
tmp-=k;
}
}
return f-tmp;
}
int ans;
int main(){
freopen("ditch.in","r",stdin);
freopen("ditch.out","w",stdout);
memset(head,-1,sizeof(head));
scanf("%d%d",&m,&n);
pos(i,1,m){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,0);
}
while(bfs()){
ans+=dfs(1,inf);
}
cout<<ans;
return 0;
}