bzoj
luogu

description

给出一张图,边有互不相同的过路费。
有 $ k $ 条边属于 $ \mbox{iriya} $ ， $ \mbox{iriya} $ 可以对这些边自己定义过路费。
现在， $ \mbox{iriya} $ 要先决定过路费，然后选择图中的一棵$ \mbox{MST} $。
然后每个点有 $ c_i $ 个人，他们会沿着这棵 $ \mbox{MST} $ 走到 $ 1 $ 号点，每个人走过一条边都要交过路费。
$ \mbox{iriya} $ 希望能最大化自己的边的过路费的收益。
\(n, m \le 300000, k \le 20\)

sol

先把 $ k $ 条边强制加入 $ \mbox{MST} $ ，然后就可以把原图缩成恰好 $ k+1 $ 个点。
然后 $ 2^k $ 暴枚每一条 $ \mbox{iriya} $ 的边选不选，然后就可以在一个规模为 $ O(k) $ 的树上跑一个 $ dp $ ，所以复杂度是 $ O(2^kk^2) $ 。

code

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi(){
    int x=0,w=1;char ch=getchar();
    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
#define ll long long
const int N = 3e5+5;
struct edge{
    int u,v,w;
    bool operator < (const edge &b) const
        {return w<b.w;}
}e[N],e1[25],e2[25];
int n,m,k,f[N],g[N],M[N];
int to[50],nxt[50],head[25],cnt,fa[25],dep[25],mn[25];
ll val[25],sum[25];
int ff(int x){return x==f[x]?x:f[x]=ff(f[x]);}
int gg(int x){return x==g[x]?x:g[x]=gg(g[x]);}
void link(int u,int v){
    to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
    to[++cnt]=u;nxt[cnt]=head[v];head[v]=cnt;
}
void dfs(int u,int f){
    fa[u]=f;dep[u]=dep[f]+1;sum[u]=val[u];
    for (int e=head[u];e;e=nxt[e])
        if (to[e]!=f) dfs(to[e],u),sum[u]+=sum[to[e]];
}
int main(){
    n=gi();m=gi();k=gi();
    for (int i=1;i<=n;++i) f[i]=g[i]=i;
    for (int i=1;i<=m;++i) e[i]=(edge){gi(),gi(),gi()};
    sort(e+1,e+m+1);
    for (int i=0;i<k;++i){
        int u=gi(),v=gi();
        e1[i]=(edge){u,v};f[ff(u)]=ff(v);
    }
    for (int i=1;i<=m;++i){
        int u=e[i].u,v=e[i].v;
        if (ff(u)^ff(v)) f[ff(u)]=ff(v),g[gg(u)]=gg(v);
    }
    int root=gg(1);
    for (int i=1,tot=0;i<=n;++i) if (gg(i)==i) M[i]=tot++;
    for (int i=1;i<=n;++i) val[M[gg(i)]]+=gi();
    for (int i=1;i<=m;++i) e[i].u=gg(e[i].u),e[i].v=gg(e[i].v);
    for (int i=0;i<k;++i) e1[i].u=gg(e1[i].u),e1[i].v=gg(e1[i].v);
    for (int i=1,top=0;i<=m;++i){
        int u=e[i].u,v=e[i].v;
        if (gg(u)^gg(v)) e2[top++]=e[i],g[gg(u)]=gg(v);
    }
    for (int i=0;i<k;++i){
        e1[i].u=M[e1[i].u],e1[i].v=M[e1[i].v];
        e2[i].u=M[e2[i].u],e2[i].v=M[e2[i].v];
    }
    root=M[root];ll ans=0;
    for (int s=1;s<(1<<k);++s){
        for (int i=0;i<=k;++i) f[i]=i,head[i]=0,mn[i]=1<<30;
        cnt=0;bool fg=0;
        for (int i=0;i<k;++i)
            if (s&(1<<i)){
                int u=ff(e1[i].u),v=ff(e1[i].v);
                if (u==v) {fg=1;break;}f[u]=v;
                link(e1[i].u,e1[i].v);
            }
        if (fg) continue;
        for (int i=0;i<k;++i){
            int u=ff(e2[i].u),v=ff(e2[i].v);
            if (u!=v) f[u]=v,link(e2[i].u,e2[i].v);
        }
        dfs(root,k+1);
        for (int i=0;i<k;++i){
            int u=e2[i].u,v=e2[i].v;
            while (u^v){
                if (dep[u]<dep[v]) swap(u,v);
                mn[u]=min(mn[u],e2[i].w);u=fa[u];
            }
        }
        ll res=0;
        for (int i=0;i<k;++i)
            if (s&(1<<i)){
                int u=e1[i].u,v=e1[i].v;
                if (dep[u]<dep[v]) swap(u,v);
                res+=sum[u]*mn[u];
            }
        ans=max(ans,res);
    }
    printf("%lld\n",ans);
    return 0;
}

[BZOJ3206][APIO2013]道路费用

原文：https://www.cnblogs.com/zhoushuyu/p/9420474.html