题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=5180
题意：给定 n 个点，m 条双向边的图。其中有 k 个点是重要的。每条边都有一定的长度。现在要你选定一些边来构成一个图，要使得 k 个重要的点相互连通，求边的长度和的最小值。
斯坦纳树裸题... 第一次写... 就是个状压 dp 嘛...
\(f_{S,i}\) 表示以 i 为根的子树，联通状态为 S 的最小费用，不同层转移是一个枚举子集的过程，同层的转移用每条边去转移，发现具有后效性，所以用最短路跑。
交了两发卡了 100s 的 OJ...
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 100005 #define M 200005 #define K 32 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,k,m; struct zgz { int next,to,val; }edge[M<<1]; int head[N],cnt=1; void add(int from,int to,int val) { edge[cnt].to=to; edge[cnt].val=val; edge[cnt].next=head[from]; head[from]=cnt++; } ll f[K][N]; int vis[N],T; inline ll Mn(ll a,ll b) {return a<b?a:b;} typedef pair<ll,int> pr; priority_queue<pr,vector<pr>,greater<pr> > q; int main() { n=read(),k=read(),m=read(); memset(f,0x3f,sizeof(f)); for(int i=0;i<k;i++)f[1<<i][read()]=0; for(int i=1;i<=m;i++) { int x=read(),y=read(),z=read(); add(x,y,z),add(y,x,z); } for(int S=1;S<(1<<k);S++) { for(int i=S;i;i=S&(i-1)) for(int j=1;j<=n;j++)f[S][j]=Mn(f[S][j],f[i][j]+f[S^i][j]); for(int i=1;i<=n;i++)q.push(make_pair(f[S][i],i)); T++; while(!q.empty()) { int x=q.top().second;q.pop(); if(vis[x]==T)continue ; vis[x]=T; for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to,val=edge[i].val; if(f[S][to]>f[S][x]+val) { f[S][to]=f[S][x]+val; q.push(make_pair(f[S][to],to)); } } } } ll ans=f[0][0]; for(int i=1;i<=n;i++) ans=Mn(ans,f[(1<<k)-1][i]); printf("%lld\n",ans); } |
Comments | NOTHING