P4784 [BalticOI2016]城市

题意：给定一个无向图，求把重要节点联通的最小代价（重要节点<=5） ------------ 将指定点集合中的所有点连通，且边权总和最小的生成树称为**最小斯坦纳树**（Minimal Steiner Tree） 其实最小生成树是最小斯坦纳树的一种特殊情况，联通了图上所有节点 最小斯坦纳树可以用dp求解 令$f[i][j]$表示以$i$为根，指定集合中点的联通状态为$j$的最小总权值 转移分为两重 - 第一重：枚举当前状态的子集进行转移 方程为：$f[i][j]=min(f[i][j],f[i][k]+f[i][j xor k])$ 枚举子集的技巧是：$for (k=j\&(j-1);k;k=j\&(k-1))$ - 第二重：在当前状态下对其进行松弛操作 方程为:$f[i][j]=min(f[i][j],f[k][j]+cost)$ 在这一重只需对这一种状态进行松弛即可，因为其他状态会通过第一重转移更新 松弛操作可以通过spfa实现（如果spfa又双叒叕被卡了请使用堆优化dijkstra） 相关题目：[JLOI2015]管道连接 [WC2008]游览计划 现在时限扩大了，加上点常数优化就可以AC了orzzzzz ~虽然我不会写fread~ ``` #include<cstdio> #include<cstring> #include<cctype> #include<queue> #include<algorithm> #define reg register using namespace std; typedef long long ll; const int N=1e5+5; struct node { int to,nxt,dis; }edge[N<<2]; struct P { int x; ll d; inline friend bool operator < (P a,P b) {return a.d>b.d;} }; int n,m,p,num,head[N]; ll f[N][32],inf,ans=1e18; bool vis[N]; priority_queue<P>q; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline void add_edge(int from,int to,int dis) { edge[++num]=(node){to,head[from],dis}; head[from]=num; } inline void dijkstra(int S) { memset(vis,0,sizeof(vis)); while (!q.empty()) { int u=q.top().x; q.pop(); if (vis[u]) continue; vis[u]=1; for (reg int i=head[u];i;i=edge[i].nxt) { int v=edge[i].to,d=edge[i].dis; if (f[v][S]>f[u][S]+d) { f[v][S]=f[u][S]+d; q.push((P){v,f[v][S]}); } } } } int main() { n=read(),p=read(),m=read(); memset(f,127/3,sizeof(f)); inf=f[0][0]; for (reg int i=1;i<=p;i++) f[read()][1<<(i-1)]=0; for (reg int i=1;i<=m;i++) { int x=read(),y=read(),z=read(); add_edge(x,y,z); add_edge(y,x,z); } for (reg int i=1;i<(1<<p);i++) { for (reg int k=1;k<=n;k++) { for (reg int j=i&(i-1);j;j=i&(j-1)) f[k][i]=min(f[k][i],f[k][j]+f[k][i^j]); if (f[k][i]<inf) q.push((P){k,f[k][i]}); } dijkstra(i); } for (reg int i=1;i<=n;i++) ans=min(ans,f[i][(1<<p)-1]); printf("%lld\n",ans); return 0; } ```