社区讨论

3376 345三个点wa了,求dalao救救蒟蒻

学术版参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mi86aea0
此快照首次捕获于
2025/11/21 09:19
4 个月前
此快照最后确认于
2025/11/21 09:19
4 个月前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10,inf=1<<29;
int ver[maxn],next[maxn],edge[maxn],tot,head[maxn];
int s,t,n,m,d[maxn],maxflow;
queue<int> q;
void add(int a,int b,int v){
	ver[++tot]=b;next[tot]=head[a];head[a]=tot;edge[tot]=v;
	ver[++tot]=a;next[tot]=head[b];head[b]=tot;edge[tot]=0;
}
int bfs(){
	memset(d,0,sizeof(d));
	while(q.size())q.pop();
	q.push(s);d[s]=1;
	while(q.size()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=next[i]){
			if(edge[i] and !d[ver[i]]){
				q.push(ver[i]);
				d[ver[i]]=d[x]+1;
				if(ver[i]==t)return 1;
			}
		}
	}
	return 0;
}
int dinic(int x,int flow){
	if(x==t)return flow;
	int rest=flow,k;
	for(int i=head[x];i and rest;i=next[i]){
		if(edge[i] and d[ver[i]]==d[x]+1){
			k=dinic(ver[i],min(rest,edge[i]));
			if(!k)d[ver[i]]=0;
			edge[i]-=k;
			edge[i^1]+=k;
			rest-=k;
		} 
	}
	return flow-rest;
}
int main(){
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;i++){
		int a,b,v;
		scanf("%d%d%d",&a,&b,&v);
		add(a,b,v);
	}
	int flow;
	while(bfs()){
		while(flow=dinic(s,inf))maxflow+=flow;
	}
	printf("%d",maxflow);
	return 0;
}
 

回复

1 条回复,欢迎继续交流。

正在加载回复...