洛谷3264 [JLOI2015]管道连接

Luogu

BZOJ

分析

斯坦纳森林。

设$f[i][S]$表示$i$号结点,与其它节点的连通性为$S$时的最小值。

这个$f$很好求,具体方法戳这里

然后,设$g[S]$表示所有频率连通性为$S$时的最小值,直接枚举子集就可以转移了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline void chkmin(int& x,int y) { if (y<x) x=y; }
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=1000+10;
const int M=3000+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].v=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt;
}

int n,m,p;
struct node { int c,id; } a[20];
int sum[N],f[N][1<<10],g[1<<10];

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 tmp[20];
inline int check(int S) {
    memset(tmp,0,sizeof(tmp));
    for (re int i=1;i<=10;++i)
        if (S&(1<<i-1)) ++tmp[a[i].c];
    for (re int i=1;i<=10;++i)
        if (tmp[i]&&tmp[i]!=sum[i]) return 0;
    return 1;
}

int main() {
    n=read(),m=read(),p=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<=p;++i)
        a[i].c=read(),a[i].id=read(),f[a[i].id][1<<i-1]=0,++sum[a[i].c];
    for (re int S=0;S<(1<<p);++S) {
        for (re int i=1;i<=n;++i) {
            for (re int sub=S;sub;sub=(sub-1)&S)
                chkmin(f[i][S],f[i][sub]+f[i][S-sub]);
            Q.push(i),inq[i]=1;
        }
        SPFA(S);
    }
    memset(g,0x3f,sizeof(g));
    for (re int S=0;S<(1<<p);++S)
        for (re int i=1;i<=n;++i)
            chkmin(g[S],f[i][S]);
    for (re int S=0;S<(1<<p);++S) {
        if (!check(S)) continue;
        for (re int sub=S;sub;sub=(sub-1)&S) {
            if (!check(sub)) continue;
            chkmin(g[S],g[sub]+g[S-sub]);
        }
    }
    printf("%d\n",g[(1<<p)-1]);
    return 0;
}
最后修改:2019 年 09 月 24 日 10 : 10 PM

发表评论