UVa12527 Kingdoms

問題
首都(ノード1)から他の都市(ノード2〜n)にアクセス可能なように辺を建設する。各辺に建設コストがあり、建設に使える総コストは K 以内に収める必要がある。各ノードに人口が与えられるので、首都にアクセス可能な人口を最大化せよ。

解法
アクセス可能なノードをビットで持ち、そのビットの状態をノードとしたグラフ上をダイクストラする。

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

#define MAX_N (1000)
#define INF (1<<29)
int N, M, K;

struct Edge {
  int to, cost;
};

typedef pair<int, int> Pii;
typedef pair<int, Pii> Piii;

vector<Edge> G[MAX_N];
int city[MAX_N];

int solve() {
  
  int ans = 0;
  int dist[1<<N];
  fill(dist, dist+(1<<N), INF);
  dist[1<<0] = 0;
  priority_queue<Pii> pq;
  pq.push(Pii(dist[1<<0], 1<<0));
  while(!pq.empty()) {
    int const cost = pq.top().first;
    int const nowS = pq.top().second;
    pq.pop();
    int sum = 0;
    for(int n=0; n<N; n++) {
      if(!(nowS >> n & 1)) continue;
      sum += city[n];
      for(int i=0; i<G[n].size(); i++) {
        Edge &e = G[n][i];
        int next = nowS|(1<<e.to);
        if(dist[next] <= cost+e.cost) { continue; }
        if(cost+e.cost > K) { continue; }

        dist[next] = cost+e.cost;
        pq.push(Pii(dist[next], next));
      }
    }
    ans = max(ans, sum);
  }
  
  return ans;
}

void ini() {
  for(int i=0; i<N; i++) G[i].clear();
}

int main() {
  
  int Tc; cin >> Tc;
  while(Tc--) {
    ini();
    cin >> N >> M >> K;
    for(int i=0; i<N; i++) { cin >> city[i]; }
    for(int i=0; i<M; i++) {
      int u, v, c; cin >> u >> v >> c;
      u --, v --;
      G[u].push_back((Edge){v, c});
      G[v].push_back((Edge){u, c});
    }
    
    cout << solve() << endl;
  }
  
  return 0;
}

メモ
初めに最小全域木やUnionFindの臭いがすると思った。感覚で何かのアルゴリズムを適用出来ないかと考えても、論理がたどり着かない場合は大抵解答できないので、臭いに従わず考えなおした。チームの人が〜〜の貪欲的な処理で解けるだろうという事を言ったような気がする。何らかの貪欲的な処理が必要だろうという気はしていたが、下手にやると WA だろうという感覚はあった。すぐにチームの人が、ダイクストラでも良いとと言った。この時点でチームの人はビットの状態をノードとして持ったダイクストラのイメージはできていた。自分はダイクストラという感覚はあった。ダイクストラは貪欲的な処理をしているので、何らかの貪欲的な処理が必要という感覚はこのことかと考えた。感覚で解法はダイクストラの方が良いのではないか、と言った。少し待ってからチームの人がダイクストラのほうが良いと言った。自分はダイクストラでどのように解くのか、と改めて考えた。まだビットの状態を持つというイメージができていなかったので、都市でダイクストラしたら失敗ではないかとチームの人に言ったがチームの人がコードを書きだして解答の真意を察した。ここでダイクストラの計算量O(|E|logV)に対して、エッジの数は問題ではないのかと考えた。しかしそれほど多くはならないのではないか？と考えなおした。