记录编号	396594	评测结果	AAAAAAAAAAAA
题目名称	草地排水	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2017-04-18 21:16:46	内存使用	0.33 MiB

#include <bits/stdc++.h>
#define MAXN 203
using namespace std;

inline int get_num() {
	int k = 0;
	char c = getchar();
	for(; !isdigit(c); c = getchar());
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k;
}

int n, m, head[MAXN];

struct edge {
	int fr, to, ne, v;
	edge() {;}
	edge(int fr_, int to_, int ne_, int v_) {
		fr = fr_, to = to_, ne = ne_, v = v_;
	}
}e[MAXN * 3];

int cnt;

inline void addedge(int fr, int to, int v) {
	e[cnt] = edge(fr, to, head[fr], v), head[fr] = cnt++;
	e[cnt] = edge(to, fr, head[to], 0), head[to] = cnt++;
}

int s, t;
int vis[MAXN], dis[MAXN], pth[MAXN];

inline bool bfs() {
	memset(vis, 0, sizeof(vis));
	memset(dis, 0, sizeof(dis));
	memset(pth, -1, sizeof(pth));
	queue <int> q;
	q.push(s);
	vis[s] = 1;
	while(!q.empty()) {
		int x = q.front();
		q.pop();
		for(int i = head[x]; ~i; i = e[i].ne) {
			int y = e[i].to;
			if(!e[i].v || vis[y]) continue;
			dis[y] = dis[x] + 1;
			pth[y] = i;
			q.push(y);
			vis[y] = 1;			
		}
	}
	return ~pth[t];
}

inline int get_flow() {
	int now = pth[t];
	int minflow = 0x7fffffff;
	while(~now) {
		minflow = min(minflow, e[now].v);
		now = pth[e[now].fr];
	}
	now = pth[t];
	while(~now) {
		e[now].v -= minflow;
		e[now ^ 1].v += minflow;
		now = pth[e[now].fr];
	}
	return minflow;
}

int main() {
	freopen("ditch.in", "r", stdin);
	freopen("ditch.out", "w", stdout);
	memset(head, -1, sizeof(head));
	n = get_num();
	m = get_num();
	s = 1;
	t = m;
	for(int i = 1; i <= n; i++) {
		int x = get_num();
		int y = get_num();
		int z = get_num();
		addedge(x, y, z);
	}
	int ans = 0;
	while(bfs()) {
		ans += get_flow();
	}
	printf("%d", ans);
	return 0;
}