如果您wa且仅wa了#10
查看原帖
如果您wa且仅wa了#10
235302
wxk123楼主2023/8/17 17:14

以我的代码为例子,请检查dfs函数中f=dfs处的参数是否打错了

#include<iostream>
#include<string.h>
#include<queue> 
using namespace std;
int N,M,S,T;
#define int long long
const int MAXN=1000500;
struct B{
	int u,v,w,next;
}p[5000005];
int head[1000500],cur[1000500],id=2;
int flag[205][205];
void build(int u,int v,int w){
	p[id].u=u;
	p[id].v=v;
	p[id].w=w;
	p[id].next=head[u];
	head[u]=id;
	id++;
}
int deep[MAXN];
bool bfs(int u,int t){queue<int>que;
	memset(deep,-1,sizeof(deep));
	for(int i=1;i<=N;i++)
	cur[i]=head[i];
	deep[u]=0;
	que.push(u);
	while(!que.empty()){
		int uu=que.front();
		que.pop();
		 for(int i=head[uu];i+1;i=p[i].next){
		 	int v=p[i].v;
			if(deep[v]==-1&&p[i].w>0){
				deep[v]=deep[uu]+1;
				que.push(v); 
				if(v==t)
				return true;
			} 
		 } 
	} 
	if(deep[t]!=-1)
	return true;
	return false;
} 
int dfs(int u,int minn){
	int left=minn;
	if(u==T||minn==0)
	return minn;
	int f=0;
	for(int i=cur[u];i+1;i=p[i].next){
		int v=p[i].v;
		if(deep[u]+1==deep[v]&&p[i].w>0&&( f=dfs(v,min(left,p[i].w)))){ //我之前这里写的是dfs(v,min(minn,p[i].w)).....
			left-=f;
			p[i].w-=f;
			p[i^1].w+=f;
		} 			
		if(!left)
			break; 
			cur[u]=i;//注意当前弧优化的位置
	}
	return minn-left;
}
int dinic(int u,int v){
	int ans=0;
	while(bfs(u,v)){
		ans+=dfs(u,0x3f3f3f3f3f3f3f3f);
	}
	return ans;
}
signed main(){
	//freopen("1.in","r",stdin);
	memset(head,-1,sizeof(head));
	memset(cur,-1,sizeof(cur));
	cin>>N>>M>>S>>T;
	for(int i=1;i<=M;i++){
		int u,v,w;
		cin>>u>>v>>w;
//		if(!flag[u][v]){
//				flag[u][v]=id;flag[v][u]=id+1;
				build(u,v,w);
				build(v,u,0);
//		}
//		else{
//			p[flag[u][v]].w+=w;
//		}
	
	}

	cout<<dinic(S,T);
	

}
2023/8/17 17:14
加载中...