AOJ 1330 : Never Wait for Weights
問題リンク : Never Wait for Weights | Aizu Online Judge
解法:
Union-Find Tree を使ってグループ分けした
各ノードは色と重さをもつものとする
最初は各ノードの色を自分の配列上でのインデックスと同じにしておく
findメソッドでは引数xが属するグループ(同じ色をもつグループ)の基準(重さが0のもの)とどれくらい差があるのかをリターンする
その差を探る過程で情報を更新する
unitメソッドでは引数xのグループを引数yのグループと併合する
この時に重みを変更するのは引数xの基準ノードだけでよい
引数xの併合前のグループの基準ノード以外のノード情報はその時に更新しなくても必要になった時(findを使われた時)に更新される
findではそのノードから基準ノードまで登っていくのでその過程で情報を更新できる
コード:
struct P { int color,w; P(int color=-inf,int w=-inf):color(color),w(w){} }; P par[MAX]; void init(){ rep(i,MAX)par[i] = P(i); } P find(int x) { if(x == par[x].color)return par[x]; P p = find(par[x].color); if(par[x].w == -inf)par[x].w = 0; par[x].w += p.w,par[x].color = p.color; return par[x]; } void unit(int x,int y,int w)//x <= y { P X = find(x); P Y = find(y); par[X.color].color = par[Y.color].color; if(par[X.color].w == -inf)par[X.color].w = 0; if(par[Y.color].w == -inf)par[Y.color].w = 0; par[X.color].w = par[X.color].w + (par[y].w-w - par[x].w); } int N,M; int main() { while(cin >> N >> M,N|M) { init(); char c; int a,b,w; rep(_,M) { cin >> c; if(c == '!') { cin >> a >> b >> w; unit(a,b,w); } else { cin >> a >> b; P B = find(b),A = find(a); if(B.color != A.color)cout << "UNKNOWN" << endl; else cout << B.w-A.w << endl; } } } return 0; }