SRM 474 500pt: TreesCount

問題概要

辺に重みの付いた連結な無向グラフが与えられる(V<50)。辺をいくつか取り除いてtreeを作りたい。ただし0から各点への最短路は辺を取り除く前と変わらないようにしたい。そのようなtreeの作り方は何通りあるか求める問題。

考えたこと

• (当時この問題見てたかどうかまったく記憶にない)
• とりあえず0からの最短路を求めよう。これはサイズ小さいからWarshall-Floydでいいや。
  • Dijkstraとか面倒だし…
• 0からの距離が近い順に決めていけばOK？
• それでいけるっぽい。自分にしては早く見えた。
• 割と実装もスムーズにできた。

practiceで通ったコード

計算量O(N^3)だけどWarshall-Floydの代わりにダイクストラすれば計算量は少し落ちる。

#include <vector>
#include <algorithm>
#include <string>
using namespace std;

typedef long long int64;

const int64 MOD = (int)(1e9 + 7);
const int INF = 1<<29;
const int MAX_N = 50;

int graph[MAX_N][MAX_N];
int graph2[MAX_N][MAX_N];
int dist[MAX_N];
bool fixed[MAX_N];

struct TreesCount {

	int count(vector <string> graph_) {
		const int N = graph_.size();

		//グラフ構成
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++){
				graph[i][j] = (graph_[i][j] == '0' ? INF : graph_[i][j] - '0');
				graph2[i][j] = graph[i][j];
			}
		}

		//最短路計算
		for(int k=0; k<N; k++){
			for(int i=0; i<N; i++){
				for(int j=0; j<N; j++){
					graph2[i][j] = min(graph2[i][j], graph2[i][k] + graph2[k][j]);
				}
			}
		}
		for(int i=0; i<N; i++){
			dist[i] = graph2[0][i];
		}

		//距離の近い順
		vector<pair<int,int> > vs;
		for(int i=1; i<N; i++){
			vs.push_back( make_pair(dist[i], i) );
		}
		sort(vs.begin(), vs.end());
		vector<int> near;
		for(int i=0; i<(int)vs.size(); i++){
			near.push_back(vs[i].second);
		}

		int64 ret = 1;
		fixed[0] = true;
		dist[0] = 0;
		for(int i=0; i<(int)near.size(); i++){
			int target = near[i], cnt = 0;
			for(int j=0; j<N; j++)if(fixed[j]){
				if(dist[target] == dist[j] + graph[j][target]){
					cnt++;
				}
			}
			fixed[target] = true;
			ret = (ret * cnt) % MOD;
		}

		return ret;
	}

};