分开输入就AC,一起输如就WA
  • 板块UVA12655 Trucks
  • 楼主_7Mr
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/11/25 17:29
  • 上次更新2023/11/25 19:20:05
查看原帖
分开输入就AC,一起输如就WA
602632
_7Mr楼主2023/11/25 17:29
#include<bits/stdc++.h>
#define int long long
#define double long double
#define INF INT_MAX
using namespace std;
const int maxn=4e5+5;
int n,m,q;
int f[maxn],fa[maxn][30],siz[maxn],p[maxn][30];
struct node{
	int x,y,z;
}a[maxn],Q[maxn];
vector<node> road[maxn];
int find(int x) {
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
bool cmp(node a,node b){return a.z>b.z;}
void dfs(int dq){
	for(int i=0;i<road[dq].size();i++){
		if(!fa[road[dq][i].y][0]){
			siz[road[dq][i].y]=siz[dq]+1;
			fa[road[dq][i].y][0]=dq;
			p[road[dq][i].y][0]=road[dq][i].z;
			dfs(road[dq][i].y);
		}
	}
	return;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	while(~scanf("%d%d%d",&n,&m,&q)){
		memset(f,0,sizeof(f));
		memset(fa,0,sizeof(fa));
		memset(siz,0,sizeof(siz));
		memset(p,0,sizeof(p));
		memset(a,0,sizeof(a));
		memset(Q,0,sizeof(Q));
		road[maxn].clear();
		for(int i=1;i<=m;i++) cin>>a[i].x>>a[i].y>>a[i].z;
		sort(a+1,a+m+1,cmp);
		for(int i=1;i<=n;i++) f[i]=i;
		for(int i=1;i<=m;i++) {
			if(find(a[i].x)==find(a[i].y)) continue;
			f[find(a[i].x)]=find(a[i].y);
			road[a[i].x].push_back(node{0,a[i].y,a[i].z});
			road[a[i].y].push_back(node{0,a[i].x,a[i].z});
		}
		for(int i=1;i<=n;i++){
			if(!fa[i][0]){
				p[i][0]=INF;
				fa[i][0]=i;
				siz[i]=1;
				dfs(i);
			}
		}
		for(int j=1;j<=20;j++){
			for(int i=1;i<=n;i++){
				fa[i][j]=fa[fa[i][j-1]][j-1];
				p[i][j]=min(p[i][j-1],p[fa[i][j-1]][j-1]);
			}
		}
		while(q--){
			int x,y;
			cin>>x>>y;
			if(find(x)!=find(y)){
				cout<<-1<<endl;
				continue;
			}
			if(siz[x]>siz[y]) swap(x,y);
			int now=20,ans=INF;
			while(siz[y]>siz[x]){
				if(siz[fa[y][now]]>=siz[x]) ans=min(ans,p[y][now]),y=fa[y][now];
				now--;
			}
			now=20;
			while(x!=y){
				if(fa[y][now]!=fa[x][now] || !now){
					ans=min(ans,min(p[x][now],p[y][now]));
					x=fa[x][now],y=fa[y][now];
				}
				if(now) now--;
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}

这个样例我分开输入就对,一起输入只有第一个对,第二个就不对了,都清空了,求助

2023/11/25 17:29
加载中...