「长乐集训 2017 Day8」修路 (斯坦纳树)

题目描述

村子间的小路年久失修，为了保障村子之间的往来，AAA君决定带领大家修路。

村子可以看做是一个边带权的无向图GGG， GGG 由 nnn 个点与 mmm 条边组成，图中的点从 1∼n1 \sim n1∼n 进行编号。现在请你选择图中的一些边，使得 ∀1≤i≤d\forall 1 \leq i \leq d∀1≤i≤d , iii 号点和 n−i+1n - i + 1n−i+1号点可以通过你选择出的那些边连通，并且你要最小化选出的所有边的权值和。请你告诉AAA君这个最小权值和。

输入格式

第一行三个整数 nnn, mmm , ddd 表示图中的点数、边数与限制条件。

接下来 mmm 行每行三个整数 uiu_iui, viv_ivi , wiw_iwi 表示一条连接 (ui,vi)(u_i, v_i)(ui,vi) 的权值为叫的无向边。

输出格式

仅一行一个整数表示答案。若无解输出 −1-1−1 .

样例

样例输入

样例输出

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = 1e4+;

 const int inf = <<;

 int fa[maxn];

 int n,m,d,ST;

 int s[maxn];

 bool inq[maxn][<<];

 int f[maxn][<<];//f[i][j]根节点为i,连同状态为j的最小生成树

 int g[<<];// g 连同状态为j的最小生成树

 int ehead[maxn],ecnt;

 queue<pair<int,int> >que;

 inline void read(int&a){char c;while(!(((c=getchar())>='')&&(c<='')));a=c-'';while(((c=getchar())>='')&&(c<=''))(a*=)+=c-'';}

 struct edge

 {

     int u,v,w,next;

 }edg[maxn*];

 bool upd(int &u,int v)

 {

     return u>v?(u=v,):;

 }

 void add (int u,int v,int w)

 {

     edg[++ecnt] = (edge){u,v,w,ehead[u]};

     ehead[u]=ecnt;

     edg[++ecnt] = (edge){v,u,w,ehead[v]};

     ehead[v]=ecnt;

 }

 int findd (int x)

 {

     if (fa[x]==x) return x;

     else return fa[x]=findd(fa[x]);

 }

 void Union (int x,int y)

 {

     int fx = findd(x),fy = findd(y);

     if (fx==fy) return ;

     else {

         fa[fx] = fy;

         return ;

     }

 }

 void spfa ()

 {

     while (!que.empty()){

         pair<int,int> h = que.front();

         que.pop();

         int u = h.first,t = h.second;

         inq[u][t] = false;

         for (int j=ehead[u];j;j=edg[j].next){

             int v = edg[j].v,k = s[v]|t;

             if (upd(f[v][k],f[u][t]+edg[j].w)&&k==t){

                 if (!inq[v][k]){

                     que.push(make_pair(v,k));

                     inq[v][k] = true;

                 }

             }

         }

     }

 }

 bool check (int j)

 {

     for (int i=;i<d;++i){

         int a = (j>>i)&;

         int b = (j>>(i+d))&;

         if (a!=b) return false;

     }

     return true;

 }

 void init ()

 {

     ecnt = ;

     for (int i=;i<maxn;++i)

         fa[i] = i;

     memset(inq,false,sizeof inq);

 }

 int main()

 {

     //freopen("road10.in","r",stdin);

     freopen("road.in","r",stdin);

     freopen("road.out","w",stdout);

     read(n);read(m);read(d);

     //scanf("%d%d%d",&n,&m,&d);

     init();

     ST=(<<(*d))-;

     for (int i=;i<=n;++i)

         for (int j=;j<=ST;++j)

             f[i][j] = inf;

     for (int i=;i<m;++i){

         int u,v,w;

         read(u);read(v);read(w);

         add(u,v,w);

         Union(u,v);

     }

     for (int i=;i<=d;++i){

         s[i] = <<(i-);

         f[i][s[i]] = ;

         s[n-i+] = <<(i-+d);

         f[n-i+][s[n-i+]] = ;

         if (findd(i)!=findd(n-i+)){

             printf("-1\n");

             return ;

         }

     }

     for (int j=;j<=ST;++j){

         for (int i=;i<=n;++i){

             for (int k=j;k>;k=((k-)&j)){//枚举j的子集k

                 upd(f[i][j],f[i][k|s[i]]+f[i][(j^k)|s[i]]);//当前根节点为i 更新

             }

         }

         for (int i=;i<=n;++i){

             if (f[i][j]<inf){

                 inq[i][j] = true;

                 que.push(make_pair(i,j));

             }

         }

         spfa();

     }

     for (int j=;j<=ST;++j){

         g[j] = inf;

         if (!check(j)) continue ;

         for (int i=;i<=n;++i)

             upd(g[j],f[i][j]);

     }

     for (int j=;j<=ST;++j){

         for (int k=j;k>;k=(k-)&j){

             upd(g[j],g[k]+g[k^j]);

         }

     }

     printf("%d\n",g[ST]);

     return ;

 }

转载:http://blog.csdn.net/gzh1992n/article/details/9119543

1. 什么是斯坦纳树？

斯坦纳树问题是组合优化学科中的一个问题。将指定点集合中的所有点连通，且边权总和最小的生成树称为最小斯坦纳树（Minimal Steiner Tree），其实最小生成树是最小斯坦纳树的一种特殊情况。而斯坦纳树可以理解为使得指定集合中的点连通的树，但不一定最小。

2. 如何求解最小斯坦纳树？

可以用DP求解，dp[i][state]表示以i为根，指定集合中的点的连通状态为state的生成树的最小总权值。

转移方程有两重：

第一重，先通过连通状态的子集进行转移。

dp[i][state]=min{ dp[i][subset1]+dp[i][subset2] }

枚举子集的技巧可以用 for(sub=(state-1)&state;sub;sub=(sub-1)&state)。

第二重，在当前枚举的连通状态下，对该连通状态进行松弛操作。

dp[i][state]=min{ dp[i][state], dp[j][state]+e[i][j] }

为什么只需对该连通状态进行松弛？因为更后面的连通状态会由先前的连通状态通过第一重转移得到，所以无需对别的连通状态松弛。松弛操作用SPFA即可。

复杂度 O(n*3^k+cE*2^k)

c为SPFA复杂度中的常数，E为边的数量，但几乎达不到全部边的数量，甚至非常小。3^k来自于子集的转移sum{C(i,n)*2^i} (1<=i<=n)，用二项式展开求一下和。

 /*

  *  Steiner Tree：求，使得指定K个点连通的生成树的最小总权值

  *  st[i] 表示顶点i的标记值，如果i是指定集合内第m(0<=m<K)个点，则st[i]=1<<m

  *  endSt=1<<K

  *  dptree[i][state] 表示以i为根，连通状态为state的生成树值

  */

 #define CLR(x,a) memset(x,a,sizeof(x))

 int dptree[N][<<K],st[N],endSt;

 bool vis[N][<<K];

 queue<int> que;

 int input()

 {

    /*

     *    输入，并且返回指定集合元素个数K

     *    因为有时候元素个数需要通过输入数据处理出来，所以单独开个输入函数。

     */

 }

 void initSteinerTree()

 {

     CLR(dptree,-);

     CLR(st,);

     for(int i=;i<=n;i++) CLR(vis[i],);

     endSt=<<input();

     for(int i=;i<=n;i++)

         dptree[i][st[i]]=;

 }

 void update(int &a,int x)

 {

     a=(a>x || a==-)? x : a;

 }

 void SPFA(int state)

 {

     while(!que.empty()){

         int u=que.front();

         que.pop();

         vis[u][state]=false;

         for(int i=p[u];i!=-;i=e[i].next){

             int v=e[i].vid;

             if(dptree[v][st[v]|state]==- ||

                 dptree[v][st[v]|state]>dptree[u][state]+e[i].w){

                 dptree[v][st[v]|state]=dptree[u][state]+e[i].w;

                 if(st[v]|state!=state || vis[v][state])

                     continue; //只更新当前连通状态

                 vis[v][state]=true;

                 que.push(v);

             }

         }

     }

 }

 void steinerTree()

 {

     for(int j=;j<endSt;j++){

         for(int i=;i<=n;i++){

             if(st[i] && (st[i]&j)==) continue;

             for(int sub=(j-)&j;sub;sub=(sub-)&j){

                 int x=st[i]|sub,y=st[i]|(j-sub);

                 if(dptree[i][x]!=- && dptree[i][y]!=-)

                     update(dptree[i][j],dptree[i][x]+dptree[i][y]);

             }

             if(dptree[i][j]!=-)

                 que.push(i),vis[i][j]=true;

         }

         SPFA(j);

     }

 }

巴特西