No.114 遠い未来 - shifth’s blog

最小シュタイナー木問題。蟻本に載っていなかった、Dreyfus-Wagnerのアルゴリズムを勉強するよい機会だった。
与えられる条件によってアルゴリズムを変える。Dreyfus-Wagnerr が使えない場合はターミナル以外の点を全探索して kruskal 法を試せば良い。
全探索時には高速化が必要。蟻本にも乗っていたけど、一行 if (mincost < cost) break; を入れて枝刈りするだけで劇的に速くなる。
出来上がった木が、単連結であること、使用するべき頂点を全て含んでいることのチェックが抜けて WA してしまった。

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;
            }
    }
};