最大流求助
查看原帖
最大流求助
750966
dulox楼主2023/11/9 22:13

写了一整天只有65,打死不用向前*的最大流,求求好心人帮忙指错

测评记录

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;

const int maxn=210;
int n,m;
struct node{
	int x,v,tni;
};
node gc(int x,int v,int tni){
	node ret;
	ret.x=x,//下一个节点的编号
	ret.v=v,//边权,正向表剩余,反向表当前
	ret.tni=tni;//反向边所在下标(lj[x][tni])
	return ret;
}
vector<node>lj[maxn];
bool book[210];
int pre[210];
int dis[210];
int deep[210];

int read(){
	char kl=getchar();
	int f=1;
	while(kl>'9'||kl<'0'){
		if(kl=='-'){
			f=-1;
		}
		kl=getchar();
	}
	int ret=0;
	while(kl>='0'&&kl<='9'){
		ret=ret*10+kl-'0';
		kl=getchar();
	}
	return f*ret;
}

bool bfs(int x){
	memset(deep,0,sizeof(deep));
	queue<int>tts;
	deep[x]=1;
	tts.push(x);
	while(!tts.empty()){
		int topt=tts.front();
		for(int i=0;i<lj[topt].size();i++){
			node topn=lj[topt][i];
			if(deep[topn.x]==0&&topn.v>0){
				deep[topn.x]=deep[topt]+1;
				tts.push(topn.x);
				if(topn.x==m){
					return true;
				}
			}
		}
		tts.pop();
	}
	return false;
}

int dfs(int x,int lowp,int t){
	if(x==t){
		return lowp;
	}
	int rest=lowp;
	for(int i=0;i<lj[x].size();i++){
		node topn=lj[x][i];
		if(deep[x]+1==deep[topn.x]&&topn.v>0){
			int k=dfs(topn.x,min(lowp,topn.v),t);
			if(k==0)deep[topn.x]=0;
			lj[x][i].v-=k;
			lj[topn.x][topn.tni].v+=k;
			rest-=k;
		}
	}
	return lowp-rest;
}

int dinic(int x){
	int maxway=0;
	while(bfs(x)){
		maxway+=dfs(x,0x3f3f3f3f,m);
	}
	return maxway;
}

int main(){
	n=read(),m=read();
	for(int i=0;i<n;i++){
		int ui=read(),wi=read(),vi=read();
		int tui=lj[ui].size(),twi=lj[wi].size();
		lj[ui].push_back(gc(wi,vi,twi));
		lj[wi].push_back(gc(ui,0,tui));
	}
	printf("%d",dinic(1));
	return 0;
} 
2023/11/9 22:13
加载中...