记录编号	192026	评测结果	AAAAAAAAAAAA
题目名称	草地排水	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.033 s
提交时间	2015-10-09 17:31:49	内存使用	0.32 MiB

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <climits>
#include <fstream>

using namespace std;
struct edge{
	int from, to, cap, flow;
};
typedef vector<edge> ve;
typedef vector<int> vi;
const int MAX(201), INF(INT_MAX / 3);
ifstream fin("ditch.in");
ofstream fout("ditch.out");
#define cin fin
#define cout fout
struct dinic{
	int n, m, s, t, flow;
	ve edges;
	vi g[MAX];
	bool vis[MAX];
	int d[MAX], cur[MAX];
	dinic(){
		n = m = s = t = flow = 0;
		fill(d, d + MAX, 0);
		edges.clear();
		for (int i = 0; i < MAX; ++i)
			g[i].clear();
	}
	void addedge(int from, int to, int cap){
		edges.push_back((edge){from, to, cap, 0});
		g[from].push_back(edges.size() - 1);
		edges.push_back((edge){to, from, 0, 0});
		g[to].push_back(edges.size() - 1);
	}
	inline void init(){
		cin >> n >> m;	//n->edge, m->node.
		for (int i = 1; i <= n; ++i){
			int si, ei, ci;
			cin >> si >> ei >> ci;
			addedge(si, ei, ci);
		}
	}
	bool bfs(){
		fill(vis + 1, vis + m + 1, false);
		queue<int> q;
		q.push(s);
		d[s] = 0;
		vis[s] = true;
		while (! q.empty()){
			int x = q.front();
			q.pop();
			for (vi::iterator it = g[x].begin(); it != g[x].end(); ++it){
				edge &e = edges[*it];
				if (! vis[e.to] && e.cap > e.flow){
					vis[e.to] = true;
					d[e.to] = d[x] + 1;
					q.push(e.to);
				}
			}
		}
		return vis[t];
	}
	int dfs(int x, int a){
		if (x == t || a == 0)
			return a;
		int flow = 0, f;
		for (int& i = cur[x]; i < g[x].size(); ++i){
			edge &e = edges[g[x][i]];
			if(d[x]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0){
				e.flow += f;
				edges[g[x][i] ^ 1].flow -= f;
				flow += f;
				a -= f;
				if (0 == a)
					break;
			}
		}
		return flow;
	}
	inline int maxflow(int s, int t){
		this->s = s, this->t = t;
		int flow = 0;
		while(bfs()){
			fill(cur + 1, cur + m + 1, 0);
			flow += dfs(s, INF);
		}
		return flow;
	}
}	dnc;

main()
{
	dnc.init();
	fin.close();
	
	cout << dnc.maxflow(1, dnc.m);
	fout.close();
//	for (; ; );
}