记录编号 217703 评测结果 AAAAAAAAAAAA
题目名称 草地排水 最终得分 100
用户昵称 Gravatarstone 是否通过 通过
代码语言 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;
}