UVA1496 Peach Blossom Spring

UVa

Luogu

分析

似乎和 JLOI2015 管道连接 差不多。

我们要求的是最小斯坦纳森林。

那么首先求出斯坦纳树,再做一遍 DP 即可求出。

设 $g_S$ 表示 $S$ 连通的最小代价,转移枚举子集即可。

注意边界只能置合法状态,也就是前 $k$ 个和后 $k$ 个的 $1$ 相等的状态。

具体实现及细节见代码。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
#define pcnt __builtin_popcount
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50+10,M=1000+10;

int n,m,k;
int f[N][1<<10],g[1<<10];

struct edge { int v,w,nxt; } e[M<<1];
int head[N],cnt=0;
inline void addEdge(int u,int v,int w) {
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}

queue<int> Q; int inq[N];
inline void spfa(int S) {
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(),inq[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (f[u][S]+w<f[v][S]) {
                f[v][S]=f[u][S]+w;
                if (!inq[v]) inq[v]=1,Q.push(v);
            }
        }
    }
}

int main() {
    int T=read();
    while (T--) {
        memset(head,0,sizeof(head)),cnt=0;
        n=read(),m=read(),k=read();
        for (re int i=1;i<=m;++i) {
            int u=read(),v=read(),w=read();
            addEdge(u,v,w),addEdge(v,u,w);
        }
        memset(f,0x3f,sizeof(f));
        for (re int i=1;i<=k;++i) f[i][1<<(i-1)]=0;
        for (re int i=n-k+1;i<=n;++i) f[i][1<<(i+k-n-1+k)]=0;
        for (re int S=0;S<(1<<(k<<1));++S) {
            for (re int i=1;i<=n;++i) {
                for (re int sub=S;sub;sub=(sub-1)&S)
                    f[i][S]=min(f[i][S],f[i][sub]+f[i][S-sub]);
                inq[i]=1,Q.push(i);
            }
            spfa(S);
        }
        memset(g,0x3f,sizeof(g));
        for (re int S=1;S<(1<<(k<<1));++S) {
            if (pcnt(S&((1<<k)-1))!=pcnt(S>>k)) continue;
            for (re int i=1;i<=n;++i) g[S]=min(g[S],f[i][S]);
        }
        for (re int S=1;S<(1<<(k<<1));++S)
            for (re int sub=S;sub;sub=(sub-1)&S)
                g[S]=min(g[S],g[sub]+g[S-sub]);
        int ans=g[(1<<(k<<1))-1];
        if (ans==0x3f3f3f3f) puts("No solution");
        else printf("%d\n",ans);
    }
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 45 PM

发表评论