为什么在#5 #7 碰钉子了?!
查看原帖
为什么在#5 #7 碰钉子了?!
773502
Billhqh9楼主2024/7/9 20:38

下面是我的代码,87分,在 #5 #7 碰钉子了。我下载了 #5 的数据,在自己电脑上跑了两遍遍结果都是正确的,但测评机给我打了WA,好神奇,为什么?

//洛谷 P3128 [USACO15DEC] Max Flow P

#include<bits/stdc++.h>

using namespace std;

const int N=50005;

struct node
{
	int to,next;
}Edge[N*2];

int n,k,x,y,Et,head[N],di[N],f[N][30],dep[N],t,p[N],ans;

void init()
{
	for(int i=1;i<=n;i++)
		head[i]=-1;
}

void add(int d1,int d2)
{
	Edge[++Et]=(node){d2,head[d1]};
	head[d1]=Et;
}

void bfs()
{
	f[1][0]=-1;
	dep[1]=0;
	queue<int>q;
	queue<int>fa;
	q.push(1);
	fa.push(-1);
	while(!q.empty())
	{
		int u=q.front(),ufa=fa.front();
		q.pop();
		fa.pop();
		for(int i=head[u];i!=-1;i=Edge[i].next)
		{
			if(Edge[i].to!=ufa)
			{
				dep[Edge[i].to]=dep[u]+1;
				f[Edge[i].to][0]=u;
				for(int j=1;j<=t;j++)
				{
					f[Edge[i].to][j]=f[f[Edge[i].to][j-1]][j-1];
				}
				q.push(Edge[i].to);
				fa.push(u);
			}
		}
	}
}

int lca(int s1,int t1)
{
	if(s1==t1)
	{
		return s1;
	}
	if(dep[s1]<dep[t1])
	{
		swap(s1,t1);
	}
	for(int i=t;i>=0;i--)
	{
		if(dep[f[s1][i]]>=dep[t1])
		{
			s1=f[s1][i];
		}
	}
	if(s1==t1)
	{
		return s1;
	}
	for(int i=t;i>=0;i--)
	{
		if(f[s1][i]!=f[t1][i])
		{
			s1=f[s1][i],
			t1=f[t1][i];
		}
	}
	return f[s1][0];
}

int dfs(int di1,int di1_father)
{
	int di1_yl=di[di1];
	for(int i=head[di1];i!=-1;i=Edge[i].next)
	{
		if(Edge[i].to!=di1_father)
		{
			di1_yl=di1_yl+dfs(Edge[i].to,di1);
		}
	}
	ans=max(ans,di1_yl);
	return di1_yl;
}

int main()
{
	
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	
	scanf("%d%d",&n,&k);
	
	t=log(n)/log(2)+1;
	
	init();
	
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	
	bfs();
	
	for(int i=1;i<=k;i++)
	{
		scanf("%d%d",&x,&y);
		di[x]++;
		di[y]++;
		int nca=lca(x,y);
		di[nca]--,di[f[nca][0]]--;
	}
	
	dfs(1,-1);
	
	printf("%d",ans);
	
	return 0;
}

2024/7/9 20:38
加载中...