読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

AOJ 1330 : Never Wait for Weights

AOJ UnionFindTree

問題リンク : 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;
}