记录编号	527273	评测结果	AAAAAAAAAAAA
题目名称	草地排水	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.046 s
提交时间	2019-02-12 21:49:05	内存使用	19.40 MiB

#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1001010;
const int INF=1e9;
int m,n,s,t,cnt=-1,head[N],ans,dep[N];
struct edge
{ int to,nx,flow;} e[N];
void add_edge(int u,int v,int w)
{ cnt++;
  e[cnt].to=v;
  e[cnt].flow=w;
  e[cnt].nx=head[u];
  head[u]=cnt;
}
bool bfs(int s,int t)
{ queue<int> que;
  memset(dep,0,sizeof(dep));
  dep[s]=1;que.push(s);
  while (!que.empty())
  { int x=que.front();que.pop();
    for (int i=head[x];i!=-1;i=e[i].nx)
    { int y=e[i].to;
      if (dep[y]==0&&e[i].flow>0)
      { dep[y]=dep[x]+1;
        que.push(y);
	  }
	}
  }
  if (dep[t]>0) return true;
  else return false;
}
int dfs(int x,int limit,int t)
{ if (x==t) return limit;
  for (int i=head[x];i!=-1;i=e[i].nx)
  { int y=e[i].to;
    if (dep[y]==dep[x]+1&&e[i].flow>0)
    { int di=dfs(y,min(limit,e[i].flow),t);
      if (di>0)
      { e[i].flow-=di;
        e[i^1].flow+=di;
        return di;
	  }
	}
  }
  return 0;
}
void dinic(int s,int t)
{  while (bfs(s,t)) ans+=dfs(s,INF,t);
}
int main()
{ freopen("ditch.in","r",stdin);
  freopen("ditch.out","w",stdout);
  scanf("%d%d",&m,&n);
  memset(head,-1,sizeof(head));
  for (int i=1;i<=m;i++)
  { int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    add_edge(x,y,z);
	add_edge(y,x,0); 
  }
  dinic(1,n);
  printf("%d",ans);
  return 0;
}