请问大佬们,能帮我找找我的代码问题在哪吗?只得20分
查看原帖
请问大佬们,能帮我找找我的代码问题在哪吗?只得20分
412042
gyy20081201楼主2022/4/21 21:20

请问大佬们,能帮我找找我的代码问题在哪吗?只得20分

#include<bits/stdc++.h>
#define N 200005
#define inf 0x3f3f3f3f
using namespace std;
struct node{
	int nxt,w,to;
}E[N];
int n,S,cnt,head[N],cur[N],deep[N],ans;
queue<int> q;
void add(int x,int y,int z){
	E[cnt].to=y;
	E[cnt].w=z;
	E[cnt].nxt=head[x];
	head[x]=cnt++;
}
bool uund(int x){
	for(int i=head[x];i;i=E[i].nxt){
		if(E[i].to!=0&&E[i].w!=0)return 0;
	}
	return 1;
}
bool bfs(){
	for(int i=1;i<=n+1;i++) cur[i]=head[i],deep[i]=-1;
	q.push(S);
	deep[S]=1;
	while(!q.empty()){
		int pp=q.front();
		q.pop();
		for(int i=head[pp];i;i=E[i].nxt){
			int v=E[i].to;
			if(E[i].w>0&&deep[v]==-1){
				deep[v]=deep[pp]+1;
				q.push(v);
			}
		}
	}
	if(deep[n+1]!=-1) return 1;
	return 0;
}
int dfs(int num,int sum){
	if(num==n+1) return sum;
	int ha=0,now;
	for(int &i=cur[num];i;i=E[i].nxt){
		int v=E[i].to;
		if(E[i].w>0&&deep[v]>deep[num]){
			now=dfs(v,min(sum-ha,E[i].w));
			if(now){
				ha+=now;
				E[i].w-=now;
				E[i^1].w+=now;
			}
		}
		if(ha==sum) return ha;
	}
	return ha;
}
int main(){
	while(~scanf("%d%d",&n,&S)){
		memset(head,0,sizeof(head));
		cnt=2,ans=0;
	    for(int i=1,a,b,c;i<n;i++){
		    scanf("%d%d%d",&a,&b,&c);
		    if(b==S||uund(b)){
		    	add(b,a,c);
		        add(a,b,0);
		        continue;
			}
		    add(a,b,c);
		    add(b,a,0);
	    }
	    for(int i=1;i<=n;i++){
	    	if(uund(i)){
	    		add(i,n+1,inf);
	    		add(n+1,i,0);
			}
		}
	    while(bfs()) ans+=dfs(S,inf);
		printf("%d\n",ans);
	}
}
2022/4/21 21:20
加载中...