10pts 只有少数点错的倍增优化建图求助
查看原帖
10pts 只有少数点错的倍增优化建图求助
508032
int08楼主2024/7/22 21:37

请问如何处理边界问题? 能不能载拓扑排序时候寻找至少经过两个关键点的环?

#include<bits/stdc++.h>
using namespace std;
#define maxv 2000000
vector<int> e[4500000],ed[124514];
int in[4500000],cnt,n,u,v,d[124514],m,i,j;
pair<int,int> f[124514][20];
void add(int u,int v)
{
//	cerr<<u<<" -> "<<v<<endl;
	if(u==v) return;
	in[v]++;
	e[u].push_back(v);
}
void dfs(int u,int fa)
{
	d[u]=d[fa]+1;
	f[u][0]={fa,++cnt};
	for(i=1;(1<<i)<=d[u];i++)
	{
		f[u][i]={f[f[u][i-1].first][i-1].first,++cnt};
		add(cnt,f[u][i-1].second),add(cnt,f[f[u][i-1].first][i-1].second);
		add(f[u][i-1].second+maxv,cnt+maxv),add(f[f[u][i-1].first][i-1].second+maxv,cnt+maxv);
	}
	for(auto v:ed[u]) if(v!=fa) dfs(v,u);
}
int s[124514],t[124514];
void color(int x,int y,int op,int u)
{
	for(int i=18;i>=0;i--) if(d[f[x][i].first]>=d[y]) add(u,f[x][i].second),add(maxv+f[x][i].second,u),x=f[x][i].first;
	if(x==y)
	{
		if(op) add(u,f[x][0].second),add(maxv+f[x][0].second,u);
		return;
	}
	for(int i=18;i>=0;i--) if(f[x][i].first!=f[y][i].first) add(u,f[x][i].second),add(maxv+f[x][i].second,u),x=f[x][i].first,add(u,f[y][i].second),add(maxv+f[y][i].second,u),y=f[y][i].first;
	if(op) add(u,f[f[x][0].first][0].second),add(maxv+f[f[x][0].first][0].second,u);
}
void lca(int x,int y,int u)
{
	if(x==y||f[x][0].first==y||f[y][0].first==x) return;
	if(d[x]<d[y]) swap(x,y);
	int xx=x,yy=y;
	for(int i=18;i>=0;i--) if(d[f[x][i].first]>=d[y]) x=f[x][i].first;
	if(x==y)
		color(f[xx][0].first,yy,0,u);
	else
		color(f[xx][0].first,f[yy][0].first,1,u);
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(i=1;i<n;i++) cin>>u>>v,ed[u].push_back(v),ed[v].push_back(u);
		dfs(1,0);
		cin>>m;
		for(i=1;i<=m;i++)
		{
			cin>>s[i]>>t[i];
			add(2*maxv+i,maxv+f[s[i]][0].second);
			add(f[t[i]][0].second,2*maxv+i);
		}
		for(i=1;i<=m;i++)
		{
//			add(2*maxv+i,f[s[i]][0].second);
			add(f[t[i]][0].second+maxv,2*maxv+i);
			lca(s[i],t[i],2*maxv+i);
		}
		queue<int> q;
		for(i=1;i<=cnt;i++)
		{
			if(in[i]==0) q.push(i);
			if(in[i+maxv]==0) q.push(i+maxv);
		}
		for(i=1;i<=m;i++) if(in[i+2*maxv]==0) q.push(i+2*maxv);
		while(!q.empty())
		{
			int u=q.front();q.pop();
//			cerr<<u<<"???"<<endl;
			for(auto v:e[u]) if(!--in[v]) q.push(v);
		 }
		bool ans=0;
		 for(i=1;i<=cnt;i++) ans=((in[i]>0)||(in[i+maxv]>0))?(ans||1):ans,	/*cerr<<in[i]<<" "<<in[i+maxv]<<' ',*/e[i].clear(),e[i+maxv].clear(),	in[i]=in[i+maxv]=0,e[i].clear(),e[i+maxv].clear();
		for(i=1;i<=m;i++) ans=(in[i+2*maxv]>0)?(ans||1):ans,/*	cerr<<in[i+2*maxv]<<" ",	*/e[i+2*maxv].clear(),in[i+2*maxv]=0,e[i+2*maxv].clear();
		cnt=0;
		puts(ans?"No":"Yes");
		for(i=0;i<=n+2;i++) d[i]=0,ed[i].clear(),memset(f[i],0,sizeof(f[i]));
	}
	return 0;
 } 
2024/7/22 21:37
加载中...