没什么可说的，第5次理解错题意了.......这里就是在并查集查找优化的时候，把权值加一下
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn=20000+10; int a[maxn],cost[maxn][maxn]; int ss; const int inf=0x3f3f3f3f; void init(int n) { for(int i=0;i<=n;i++) a[i]=i; memset(cost,inf,sizeof(cost)); for(int i=0;i<=n;i++) cost[i][i]=0; } int dfs(int x) { if(a[x]==x) return x; int mm=a[x]; a[x]=dfs(a[x]); cost[x][a[x]]=cost[x][mm]+cost[mm][a[x]];//权值相加 return a[x]; } int n,t; int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); init(n); getchar(); char c; while(1) { scanf("%c",&c); getchar(); if(c=='O') break; int aa,bb; if(c=='E') { scanf("%d",&aa); dfs(aa); int cnm=cost[aa][a[aa]]; printf("%d\n",cnm); } else if(c=='I') { scanf("%d%d",&aa,&bb); cost[aa][bb]=abs(aa-bb)%1000; a[aa]=bb; } getchar(); } } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/7390157.html
