萌新求助!
  • 板块学术版
  • 楼主A524
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/2/21 18:14
  • 上次更新2023/11/5 02:55:43
查看原帖
萌新求助!
484922
A524楼主2021/2/21 18:14

HDU2874这题我Runtime Error(ACCESS_VIOLATION)。贴上我的程序:

#include<iostream>
#include<cstdio>
#include<vector>
#define maxn 100100
using namespace std;
vector<int> a[maxn],b[maxn];
int Mi[maxn][20],o[maxn],ha[maxn],fist[maxn],D[maxn],dep[maxn],F[maxn],lo2[maxn],Min,tot,X,Y,x,y,z,n,m,t,i,S,k,j;
int fin(int x){return (F[x]==x)?x:F[x]=fin(F[x]);}
void dfs(int x,int y,int DEP){
	o[++t]=x;fist[x]=t;dep[t]=DEP;
	int i;
	for (i=0;i<a[x].size();i++)
		if (a[x][i]!=y)
			D[a[x][i]]=D[x]+b[x][i],dfs(a[x][i],x,DEP+1),o[++t]=x,dep[t]=DEP;
	return ;
}
int main(){
	while (~scanf("%d %d %d",&n,&m,&k)){	
		for (i=1;i<=n;i++) F[i]=i;
		for (i=1;i<=m;i++){
			scanf("%d %d %d",&x,&y,&z);
			a[x].push_back(y);b[x].push_back(z);
			a[y].push_back(x);b[y].push_back(z);
			F[fin(x)]=y;
		}
		for (i=1;i<=n;i++)
			if (fin(i)==i)
				dfs(i,0,1);
		for (i=2;i<=n;i++) lo2[i]=lo2[i>>1]+1;
		for (i=1;i<=n;i++) Mi[i][0]=i;
		for (j=1;j<=lo2[n];j++)
			for (i=1;i<=n;i++)
				X=dep[Mi[i][j-1]],Y=dep[Mi[i+(1<<(j-1))][j-1]],Mi[i][j]=(X<Y)?X:Y;
		for (i=1;i<=k;i++){
			scanf("%d %d",&x,&y);
			if (fin(x)!=fin(y)){printf("Not connected\n");continue;}
			S=D[x]+D[y];
			x=fist[x];y=fist[y];
			if (x>y) swap(x,y);
			k=lo2[y-x+1];
			X=dep[Mi[x][k]];Y=dep[Mi[y+1-(1<<k)][k]];
			Min=(X<Y)?X:Y;
			S-=2*D[o[Min]];
			printf("%d\n",S);
		}	
	}
	return 0;
} 
2021/2/21 18:14
加载中...