[题解] P3639 [APIO2013]道路费用

· · 题解

发现 k 很小，只有 20，那么这题复杂度大概率和 2^k 有关

考虑枚举加入新边的集合，如果直接跑最小生成树的话会 T，需要优化

容易发现每次最小生成树重复加入的边数会很多，于是可以考虑哪些边是一定会加入

我们先把 k 条边全部加入，接下来跑一边最小生成树，原图上的边如果在这个最小生成树里那么就是一定会加入的边，设这个边集为 \mathcal S（由于题目条件里有边权互不相同，于是这个最小生成树唯一）

接下来把这些边组成的连通块缩成一个点，有 k+1 个点，再用原图边跑一遍这 k+1 个点上的最小生成树，得到的边集（设为 \mathcal T）即为可能出现在之后的最小生成树里的边

现在在枚举边集的时候跑的最小生成树只要在缩点后的图上把枚举的边集加入再用刚才得到的边集跑最小生成树就行了

接下来需要计算每个新边的边权最大值

对于一棵生成树 \mathscr T，和一个不在 \mathscr T 上的边 e，如果把 e 加到 \mathscr T 上，那么一定会出现一个环。如果环上存在一条边的边权比 e 的边权大，则 \mathscr T 一定不是最小生成树

我们可以用这个性质来约束边权

对于 \mathcal T 中的一条边 e: u\to v，它可以约束树上 u\to v 路径上所有的边的边权都需要小于等于它的边权

于是这个可以用一个 lca 搞定，当然这里只有 k+1 个点，所以暴力爬树就行

最后还要计算每条边有多少人通过，这个用一遍 dfs 求子树大小就可以求出来了

代码比较烦，但是细节还是比较少的 （所以为什么我一个 ; 写成 , 还能得 35pts 啊）

时间复杂度 \mathcal O(m\log m+2^kk^2)

code:

#include<bits/stdc++.h>
#define MAXN 300010
#define MAXK 30
#define int long long
using namespace std;
int n,m,K,tot,a[MAXN];
struct Node{int fr,to,val;}e[MAXN],ne[MAXN],que[MAXN];
bool cmp(Node a,Node b){return a.val<b.val;}
int f[MAXN],g[MAXN];
int getf(int x){return f[x]==x?x:f[x]=getf(f[x]);}
int getg(int x){return g[x]==x?x:g[x]=getg(g[x]);}
int col[MAXN],cnt,val[MAXK];
void kruskal(){
    for(int i=1;i<=n;i++)f[i]=g[i]=i;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=K;i++){
        int u=ne[i].fr,v=ne[i].to;
        int a=getf(u),b=getf(v);
        if(a==b)continue;
        f[a]=b;
    }
    for(int i=1;i<=m;i++){
        int u=e[i].fr,v=e[i].to;
        int a=getf(u),b=getf(v);
        if(a==b)continue;
        f[a]=b;
        a=getg(u),b=getg(v);
        if(a<b)swap(a,b);g[a]=b;
    }
    for(int i=1;i<=n;i++){
        if(getg(i)==i)col[i]=++cnt,val[cnt]=a[i];
        else col[i]=col[getg(i)],val[col[i]]+=a[i];
    }
    for(int i=1;i<=K;i++){
        int u=ne[i].fr,v=ne[i].to;
        ne[i]=(Node){col[u],col[v],0};
    }
    for(int i=1;i<=m;i++){
        int u=e[i].fr,v=e[i].to,w=e[i].val;
        int a=getg(u),b=getg(v);
        if(a==b)continue;
        que[++tot]=(Node){col[u],col[v],w};
        if(a<b)swap(a,b);g[a]=b;
    }
}
struct tnode{int to,nxt;}Edge[MAXK<<1];
int cnt_Edge,Head[MAXK];
void Add_Edge(int u,int v){
    Edge[++cnt_Edge]=(tnode){v,Head[u]};
    Head[u]=cnt_Edge;
}
int fa[MAXK],dep[MAXK],mn[MAXK],sz[MAXK];
void dfs(int u,int fat){
    fa[u]=fat;dep[u]=dep[fat]+1;sz[u]=val[u];
    for(int i=Head[u];i;i=Edge[i].nxt){
        int v=Edge[i].to;if(v==fat)continue;
        dfs(v,u);sz[u]+=sz[v];
    }
}
void update(int u,int v,int w){
    while(u!=v){
        if(dep[u]>dep[v])swap(u,v);
        mn[v]=min(mn[v],w);v=fa[v];
    }
}
signed main(){
    scanf("%lld%lld%lld",&n,&m,&K);
    for(int i=1;i<=m;i++){
        int u,v,w;scanf("%lld%lld%lld",&u,&v,&w);
        e[i]=(Node){u,v,w};
    }
    for(int i=1;i<=K;i++){
        int u,v;scanf("%lld%lld",&u,&v);
        ne[i]=(Node){u,v,0};
    }
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    kruskal();int ans=0,rt=col[1];
    for(int s=0;s<(1<<K);s++){
        memset(Head,0,sizeof(Head));cnt_Edge=0;
        memset(fa,0,sizeof(fa));memset(dep,0,sizeof(dep));
        memset(mn,0x3f,sizeof(mn));memset(sz,0,sizeof(sz));
        for(int i=1;i<=cnt;i++)f[i]=i;bool fl=false;
        for(int i=1;i<=K;i++){
            if(!((s>>(i-1))&1))continue;
            int u=ne[i].fr,v=ne[i].to;
            int a=getf(u),b=getf(v);
            if(a==b){fl=true;break;}
            f[a]=b;Add_Edge(u,v);Add_Edge(v,u);
        }if(fl)continue;
        for(int i=1;i<=tot;i++){
            int u=que[i].fr,v=que[i].to;
            int a=getf(u),b=getf(v);
            if(a==b)continue;
            f[a]=b;Add_Edge(u,v);Add_Edge(v,u);
        }dfs(rt,0);
        for(int i=1;i<=tot;i++){
            int u=que[i].fr,v=que[i].to,w=que[i].val;
            update(u,v,w);
        }int res=0;
        for(int i=1;i<=K;i++){
            if(!((s>>(i-1))&1))continue;
            int u=ne[i].fr,v=ne[i].to;
            if(dep[u]<dep[v])swap(u,v);
            res+=mn[u]*sz[u];
        }ans=max(ans,res);
    }printf("%lld",ans);
    return 0;
}