結果
| 問題 |
No.114 遠い未来
|
| コンテスト | |
| ユーザー |
 codershifth
|
| 提出日時 | 2015-10-11 23:37:37 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 1,088 ms / 5,000 ms |
| コード長 | 6,975 bytes |
| コンパイル時間 | 1,789 ms |
| コンパイル使用メモリ | 186,592 KB |
| 実行使用メモリ | 6,016 KB |
| 最終ジャッジ日時 | 2024-07-21 07:02:50 |
| 合計ジャッジ時間 | 8,565 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 25 |
ソースコード
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()
class UFTree {
std::vector<int> par_;
std::vector<int> rank_;
public:
UFTree(int N) { init(N); }
UFTree() {}
~UFTree() {}
void init(int N) {
par_.resize(N);
rank_.resize(N, 0);
for (int i = 0; i < N; ++i)
par_[i] = i;
}
int find(int x) {
if ( par_[x] == 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;
if ( rank_[x] < rank_[y] )
par_[x] = y;
else
{
par_[y] = x;
if ( rank_[x] == rank_[y] )
++rank_[x];
}
}
bool same(int x, int y) {
return (find(x) == find(y));
}
int operator[](size_t i) { return find(i); }
};
template <typename T>
class MinSteinerTree
{
public:
using matrix = std::vector<std::vector<T>>;
matrix graph_;
MinSteinerTree() {}
MinSteinerTree(int n) { init(n); }
T inf() { return (1<<29); }
void init(int n)
{
graph_.resize(n);
for (int i = 0; i < n; ++i)
graph_[i].resize(n,inf());
for (int i = 0; i < n; ++i)
graph_[i][i] = 0;
}
void add(int u, int v, T c) { graph_[u][v] = graph_[v][u] = c; }
T solve(const std::vector<T> &t) { return solve(t, graph_); }
T solve(const std::vector<T> &t,
const std::vector<std::vector<int>> &g)
{
const int n = g.size();
const int nt = t.size();
if (nt <= 1)
return 0;
matrix d(g); //最短距離
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
// opt[S][p] := S をターミナルとし p を含む最小シュタイナー木を作成するときのコスト
matrix opt(1<<nt, std::vector<T>(n, inf()));
// 各ターミナルから直接つなげる部分を先に計算
for (int p = 0; p < nt; ++p)
for (int q = 0; q < n; ++q)
opt[1<<p][q] = d[t[p]][q];
// DP で最適コストを計算する。 O(4^|t|*n^2)
for (int S = 1; S < (1<<nt); ++S)
{
if ( !(S & (S-1)) ) // 部分集合がないなら飛ばす
continue;
// S を分割して更新してみる
for (int p = 0; p < n; ++p)
for (int E = (S-1)&S; E; E = (E-1)&S) // O(|S|) <= O(2^|t|) (部分集合を回る)
opt[S][p] = std::min(opt[S][p], opt[E][p] + opt[S-E][p]);
// 辺を追加して更新してみる
for (int p = 0; p < n; ++p)
for (int q = 0; q < n; ++q)
opt[S][p] = std::min(opt[S][p], opt[S][q] + d[p][q]);
}
T ans = inf();
for (int S = 0; S < (1<<nt); ++S)
for (int q = 0; q < n; ++q)
ans = std::min(ans, opt[S][q] + opt[((1<<nt)-1)-S][q]);
return ans;
}
};
using namespace std;
class TheDistantFuture
{
public:
void solve(void)
{
int N,M,T;
cin>>N>>M>>T;
vector<tuple<int,int,int>> edge;
MinSteinerTree<int> mst(N);
REP(i,M)
{
int a,b,c;
cin>>a>>b>>c;
--a,--b;
mst.add(a,b,c);
edge.emplace_back(c,a,b); // sort のため cost を先頭に入れておく
}
vector<int> t(T);
REP(i,T)
{
int tmp;
cin>>tmp;
--tmp;
t[i] = tmp;
}
if (T <= 14)
cout<<mst.solve(t)<<endl;
else
{
vector<int> idx(N); // index 参照用
int k = 0;
REP(v,N)
{
if (find(RANGE(t), v) != t.end())
idx[v] = -1;
else
idx[v] = k++;
}
int mincost = (1<<30);
// T が大きいときは T を除いた残りの頂点のうちどれを使うかの 2^(N-T) 通りを全探索する。
// kruskal 法
sort(RANGE(edge)); // cost が小さい順に並べる
// O(2^(N-T)*M)
for (int R = 0; R < (1<<(N-T)); ++R)
{
const auto inf = (1<<30);
UFTree uft(N); // O(N)
vector<bool> used(N,false);
int cost = 0;
int nR;
for (auto e : edge)
{
int a,b,c;
int ia,ib;
tie(c,a,b) = e;
ia = idx[a];
ib = idx[b];
// 端点が t にも R にも含まれていないなら飛ばす
if ( ia >= 0 && !((1<<ia) & R) )
continue;
if ( ib >= 0 && !((1<<ib) & R) )
continue;
// 連結済みなら飛ばす
if (uft.same(a,b))
continue;
uft.unite(a,b);
used[a] = used[b] = true;
cost += c;
// 枝刈り
if ( cost > mincost )
{
cost = inf;
break;
}
}
// 出来上がった木が単連結になっているか確認
nR = 0;
REP(v,N)
{
// 単連結か？
if (used[v] && uft[t[0]] != uft[v])
cost = inf;
if ((1<<idx[v]) & R)
++nR;
}
// set(R) u set(t) をカバーしているか？
if (nR + T != count(RANGE(used),true))
cost = inf;
mincost = min(mincost, cost);
}
cout<<mincost<<endl;
}
}
};
#if 1
int main(int argc, char *argv[])
{
ios::sync_with_stdio(false);
auto obj = new TheDistantFuture();
obj->solve();
delete obj;
return 0;
}
#endif