保存されている過去のバージョンの一覧

2014年05月24日04時39分19秒

TopCoder SRM621 DIV1 MEDIUM - TreesAnalysis

Source

TopCoder SRM621 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

ノード数 $N$ の無向グラフが $2$ 個，$G_1,G_2$ が与えられる．
ノードは，それぞれのグラフで，$0,1,\ldots,N-1$ の番号が付けられている．
グラフ $G_1$ の枝 $e_1$ と，グラフ $G_2$ の枝 $e_2$ に対して $S(e_1,e_2)$ を次のように定める．
グラフ $G_k$ から枝 $e_k$ を取り除くと $2$ つの連結グラフに分かれるが，それをグラフ $X_k,Y_k$ とする（$k=1,2$）．
$X_1,X_2$ に両方含まれているノード番号，$X_1,Y_2$ に両方含まれているノード番号，$Y_1,X_2$ に両方含まれているノード番号，$Y_1,Y_2$ に両方含まれているノード番号，の $4$ つのうちで最も大きい数を $S(e_1,e_2)$ とする．
全ての枝のペア $(e_1,e_2)$ に対する $S(e_1,e_2)$ の自乗和
　　$\displaystyle \sum_{(e_1,e_2)} S(e_1,e_2)^2$
を求める問題．

解法

要するに $S(e_1,e_2)$ を全部計算すれば良い．
まず，グラフ $G_1$ において，どの枝を取り除くパターン $N-1$ 通りは愚直に全部行う．
その際，DFSなどで片方の連結グラフ $X_1$ に含まれるノードを列挙して，$O(1)$ で判定できるようにしておく．また，$X_1$ に含まれるノード数も計算しておく．
グラフ $G_2$ においては，根付き木と考える．
各ノードについて，自分と自分の子供以下のノードのなかで，$X_1$ に含まれるノード番号のノードがいくつあるか，含まれないノードがいくつあるかを葉の方から順番に計算していく．
すると，各ノードについて，自分とその親をつなぐ枝を $e_2$ として取り除く場合の $S(e_1,e_2)$ は $O(1)$ で計算できるようになる．
合計で時間計算量 $O(N^2)$．

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

int N;
int edge1[4100][4100], es1[4100];
int edge2[4100][4100], es2[4100];
ll res;

int del1, del2;
int colored[4100], colored_all;
void dfs1(int now, int bef){
  int i, k;

  colored[now] = 1;
  colored_all++;
  rep(i,es1[now]){
    k = edge1[now][i];
    if(k==bef) continue;
    if(now==del1 && k==del2) continue;
    if(now==del2 && k==del1) continue;
    dfs1(k, now);
  }
}

int dp[4100], all[4100];
void dfs2(int now, int bef){
  int i, k, mx;

  dp[now] = colored[now];
  all[now] = 1;
  rep(i,es2[now]){
    k = edge2[now][i];
    if(k==bef) continue;
    dfs2(k, now);
    dp[now] += dp[k];
    all[now] += all[k];
  }

  if(bef != -1){
    mx = max(dp[now], all[now]-dp[now]);
    mx = max(mx, colored_all - dp[now]);
    mx = max(mx, N - colored_all - all[now] + dp[now]);
    res += mx*mx;
  }
}

class TreesAnalysis {
public:
ll treeSimilarity(vector <int> tree1, vector <int> tree2) {
  int i, j, k, d;

  N = tree1.size() + 1;
  res = 0;

  rep(i,N) es1[i] = es2[i] = 0;
  rep(i,N-1){
    j = tree1[i];
    edge1[i][es1[i]++] = j;
    edge1[j][es1[j]++] = i;
    j = tree2[i];
    edge2[i][es2[i]++] = j;
    edge2[j][es2[j]++] = i;
  }

  rep(d,N-1){
    rep(i,N) colored[i] = 0; colored_all = 0;
    del1 = d;
    del2 = tree1[d];
    dfs1(0, -1);
    dfs2(0, -1);
  }

  return res;
}

}

Current time: 2024年04月20日15時29分55秒
Last modified: 2014年05月24日04時39分19秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM621 SRM_Div1_Medium
トップページに戻る

Logged in as: unknown user (not login)

ログイン：