网络流萌新求助
查看原帖
网络流萌新求助
429499
isletfall楼主2023/12/14 21:26

我在写这道题的时候,刚开始我是这么写的:

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+7;
struct node{
	long long v,w,nxt;
}e[maxn];
long long head[maxn],dpt[maxn],cur[maxn],cnt;
long long max_flow,t;
int n,m,x;
void add(long long x,long long y,long long z){
	e[++cnt].v=y;
	e[cnt].w=z;
	e[cnt].nxt=head[x];
	head[x]=cnt;
}
bool bfs(){
	queue<int> q;
	for(int i=1;i<=n;i++)
	dpt[i]=0;
	dpt[1]=1;
	q.push(1);
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(int i=head[now];i;i=e[i].nxt){
			int y=e[i].v;
			if(e[i].w>0&&dpt[y]==0){
				q.push(y);
				dpt[y]=dpt[now]+1;
				if(y==n)return 1;
			}
		}
	}
	return 0;
}
long long dfs(long long x,long long flow){
	if(x==n)return flow;
	long long res=flow;
	for(int i=cur[x];i&&flow;i=e[i].nxt){
		cur[x]=i;
		long long y=e[i].v;
		if(e[i].w>0&&dpt[y]==dpt[x]+1){
			long long k=dfs(y,min(res,e[i].w));
			if(k==0)dpt[y]=0;
			e[i].w-=k;
			e[i^1].w+=k;
			res-=k;
		}
	}
	return flow-res;
}
int main(){
	cin>>n>>m>>x;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,0);
	}
	int flow=0;
	while(bfs()){
		for(int i=1;i<=n;i++)
		cur[i]=head[i];
		while(flow=dfs(1,1<<29))max_flow+=flow;
	}
	if(max_flow==0)puts("Orz Ni Jinan Saint Cow!");
	else{
	t=x/max_flow;
	if(x%max_flow!=0)t++;
	cout<<max_flow<<" "<<t;	
	}
	return 0;
}
结果我只拿到了80pts
但是我后来把cnt的初值设成了1,结果AC了这道题,有没有大佬能给我解释一下其中的问题吗
2023/12/14 21:26
加载中...