记录编号	587079	评测结果	AAAAAAAAAAAA
题目名称	草地排水	最终得分	100
用户昵称	Untitled	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2024-03-12 20:44:59	内存使用	0.00 MiB

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

int const N=210;
int n,m,idx,res,level[N];
int head[N],Next[N*2],ver[N*2],val[N*2];
bool d[N];

struct node{
	int x,lv;
};

void edge(int a,int b,int v){
	Next[++idx]=head[a],head[a]=idx,ver[idx]=b,val[idx]=v;
	Next[++idx]=head[b],head[b]=idx,ver[idx]=a;
	return;
}

bool bfs(){
	queue<node> q;
	memset(d,0,sizeof(d));
	q.push(node{1,1});
	int y;
	node t;
	while (q.size()){
		t=q.front();q.pop();
		d[t.x]=1;
		if (!level[t.x]) level[t.x]=t.lv;
		else level[t.x]=min(level[t.x],t.lv);
		for (int i=head[t.x];i;i=Next[i]){
			y=ver[i];
			if (d[y] || !val[i]) continue;
			q.push(node{y,t.lv+1});
		}
	}
	return level[m];
}

int dfs(int x,int minn){
	if (x==m) return minn;
	int y,k,cnt=0;
	for (int i=head[x];i;i=Next[i]){
		y=ver[i];
		if (!val[i] || level[x]+1!=level[y]) continue;
		k=dfs(y,min(minn,val[i]));
		minn-=k,cnt+=k,val[i]-=k;
		val[i^1]+=k;
		if (!minn) break;
	}
	return cnt;
}

int main(){
	freopen("ditch.in","r",stdin);
	freopen("ditch.out","w",stdout);
	
	int a,b,v;
	scanf("%d %d",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%d %d %d",&a,&b,&v);
		edge(a,b,v);
	}
	while (bfs()){
		res+=dfs(1,INT_MAX);
		memset(level,0,sizeof(level));
	}
	printf("%d",res);
	
	return 0;
}