ICPC アジア地区予選2012 F Never Wait for Weights

問題

Never Wait for Weights | Aizu Online Judge

問題概要

N個の重りとM個のクエリがあるので、各クエリについて処理してください。
クエリとしては以下の2つが与えられます。
! A B W := Bの重さ-Aの重さがWであることが分かった
? A B := Bの重さ-Aの重さを出力する。ただし、このクエリを処理する時点でBの重さとAの重さの差がわからなかったら文字列としてUNKNOWNを出力する。

解法

ぱっと思いつくのは!クエリがきたら各頂点間にWの辺を張り、?クエリがきたらAから幅優先探索をしてBにたどり着いたらその時のコストを出力、たどり着かなかったらUNKNOWNを出力する、というものだが、これだとO(NM)で間に合わない。
よく考えると、ある時点でAとBの距離が求められる(UNKNOWNではない)ようになったら、その後にAとBが所属しているグラフに対して新たな辺がはられたとしてもAとBの距離は変わらないし、その逆も言える。従って、まずはクエリの先読みをして、各頂点間の距離の関係を求める。

クエリの先読みでは一つ目のクエリに関して森を構築する。その際、A->BにWの辺を貼ると共にならであることからB->Aに-Wの辺も張る。このとき、A,Bは必ず閉路となってしまうが、これは一つの無向辺のようなものとしてみなす。ある辺を追加すると木にならないような辺は張る必要はなく、なぜならある頂点iとjが連結でありさえすればiとjの重さの差を知ることができ、また、?クエリを処理するときに木であったほうが計算が楽になる。(後述の図を参照)

森を作ることができたら、各頂点についてその頂点が属している木の根(任意の頂点を根にしてよい)からの距離lengthを計算する。木であることを利用すると根から幅優先探索or深さ優先探索をしていけばよい。

最後に、もう一度クエリを最初から見ていき、次のような処理を行っていけば答えを出すことができる。
!クエリ: AとBを同じグループに所属させる。
?クエリ:その時点でAとBが同じグループに属していなければ重さの差を知ることができないのでUNKNOWNを出力する。そうでなければ、length[B] - length[A]を出力する。

length[A], length[B]はAとBが属している木の根からの距離なので、図からlength[B] - length[A] = (a + c) - (a + b) = c - bとなっているので、AとBの距離の差を計算することができる。

計算時間はO(M + N)

コード

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>
 
#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long

using namespace std;

typedef pair<int, int> II;

#define MAX_N 100005
#define MAX_M 100005

int N, M;
char Query[MAX_M];
int A[MAX_M], B[MAX_M], W[MAX_M];

bool Input(){
  cin >> N >> M;
  if((N || M) == 0)
    return false;
  for(int i = 0; i < M; i++){
    cin >> Query[i]; scanf("%d %d", &A[i], &B[i]);
    A[i]--; B[i]--;
    if(Query[i] == '!'){
      scanf("%d", &W[i]);
    }
  }
  return true;
}

int par[MAX_N];
void Init(){
  for(int i = 0; i < MAX_N; i++){
    par[i] = i;
  }
}
int find(int x){
  if(x == par[x])
    return x;
  else
    return par[x] = find(par[x]);
}
void unite(int x, int y){
  x = find(x);
  y = find(y);
  if(x == y)
    return;
  par[y] = x;
}
bool same(int x, int y){
  return find(x) == find(y);
}

vector<II> G[MAX_N];

void MakeEdge(){

  for(int i = 0; i < N; i++){
    G[i].clear();
  }
  Init();
  for(int i = 0; i < M; i++){
    if(Query[i] == '!'){
      if(!same(A[i], B[i])){
	unite(A[i], B[i]);
	G[A[i]].push_back(II(B[i], W[i]));
	G[B[i]].push_back(II(A[i], -W[i]));
      }
    }
  }

}

//親ノードからの距離
int length[MAX_N];
bool used[MAX_N];

void CalcLength(){

  memset(used, 0, sizeof(used));
  for(int i = 0; i < N; i++){
    if(!used[find(i)]){
      queue<II> que;
      que.push(II(find(i), 0));
      used[find(i)] = true;
      length[find(i)] = 0;
      
      while(que.size()){
	II p = que.front();
	que.pop();
	int pos = p.first;
	int len = p.second;
	for(int i = 0; i < (int)G[pos].size(); i++){
	  int next = G[pos][i].first;
	  int nextCost = len + G[pos][i].second;
	  if(!used[next]){
	    used[next] = true;
	    length[next] = nextCost;
	    que.push(II(next, nextCost));
	  }
	}
      }
    }
  }

}

void Solve(){

  //クエリを先読みして木を作成する
  MakeEdge();

  //各頂点iの親から、iまでの距離を計算する
  CalcLength();

  Init();

  for(int i = 0; i < M; i++){
    if(Query[i] == '!'){
      unite(A[i], B[i]);
    }
    else{
      if(!same(A[i], B[i])){
	cout << "UNKNOWN" << endl;
      }
      else{
	cout << length[B[i]] - length[A[i]] << endl;
      }
    }
  }

}

int main(){

  while(Input()){
    Solve();
  }
  
  return 0;
  
}