记录编号	587069	评测结果	RRRRRRRRRR
题目名称	运输问题1	最终得分	0
用户昵称	Untitled	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2024-03-12 19:30:04	内存使用	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]=b,val[idx]=0;
	return;
}

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

int dfs(int x,int minn){
	if (x==m) return minn;
	int y,k,cnt=0;
	d[x]=1;
	for (int i=head[x];i;i=Next[i]){
		y=ver[i];
		if (d[y] ||!val[i]) continue;
		k=dfs(y,min(minn,val[i]));
		minn-=k,cnt+=k,val[i]-=k;
		if (i%2) val[i+1]+=k;
		else val[i-1]+=k;
		if (!minn) break;
	}
	d[x]=0;
	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()){
		memset(d,0,sizeof(d));
		res+=dfs(1,INT_MAX);
		memset(level,0,sizeof(level));
	}
	printf("%d",res);
	
	return 0;
}