道路费用 APIO2013

WZH2026-10-012026-10-01

[APIO2013] 道路费用

Great!

[APIO2013] 道路费用。

有一张 $n$ 点 $m$ 边的带权图。还有 $k$ 条额外道路，但是权值未定。你需要设置这些边的权值，使得取这个图的最小生成树（若有多个则任选一条）后，所有节点到节点 $1$ 的带权路径和最大（计算且仅计算额外的 $k$ 条边带来的收益）。求最大权值。

$n\le 10^5,m\le 3\times10^5,k\le 20$ 。

警示后人：

复杂度很容易写假，注意细节。

首先观察数据范围，猜测这是一个 $\mathcal{O}(2^kk)$ 或 $\mathcal{O}(2^kk^2)$ 的算法。

因此不妨考虑枚举哪些额外的边做贡献（特别的，若这枚举的边有环，则此次枚举不合法，略去）。然后通过最小生成树的限制，用其他的非树边对这些边进行限制。

具体的，对于枚举的一组额外的边，先提前将他们加入。然后模拟 Kruskal 的过程：

当遇到一条树边时，直接加入它。
当遇到一条非树边时，由于最小生成树的性质，它的权值必然 $\ge$ 最小生成树的对应的链上最大边权。因此对应链上的所有没有确定边权的边，他们的权值必须是这条边的边权。

这样就调整完了，直接模拟可以做到 $\mathcal{O}(2^knk)$ ，可以拿下 $56$ 分。

然而我就不会优化了。

此时想要优化，必然要从复杂度瓶颈去考虑：枚举原图的边的过程。

想一想，这里面的边，有一些一定是树边，一些一定不是树边，一些可能成为树边。我们要从这一方面去考虑优化。

先看一定是树边的边。这些边必然在我已经加入了所有额外的边后，仍然需要加入。因此我们先将所有额外的边加入，然后跑 Kruskal，加入的边就是所有必然为树边的边。

因为这些边必然加入，所以我们不妨用这些边先缩点，这样就会有 $k+1$ 个缩点后的点。**这样总点数就下来了！**然后我们对着缩点后的图跑 Kruskal，得到的边就是所有可能加入的边。这些边不会超过 $k$ 条！

接下来就好说了。枚举所有可能的额外的边的组合，然后将他们连在一起。再用所有可能加入的边去更新最小生成树，以及所有未确定边权的额外的边。最后对着缩点后的图跑 dfs 就行。

然后就解决了。代码：

#include <bits/stdc++.h>
using namespace std;
const int N=300010;
#define int long long
int n,m,k,sz[N],id[N],p[N],SZ[N];
struct node{int u,v,w;}q[N],qe[N],qn[N],Q[N];
struct dsu{
    int f[N],sz[N];
    void init(int n){
        for(int i=1;i<=n;i++)
            f[i]=i,sz[i]=p[i];
    }
    int getf(int x){return f[x]==x?x:f[x]=getf(f[x]);}
    void add(int x,int y){
        x=getf(x),y=getf(y);
        if(x!=y)f[y]=x,sz[x]+=sz[y];
    }
    bool in(int x,int y){return getf(x)==getf(y);}  
}A;
const int inf=1e18;
int mn[N],f[N],d[N];
bool operator<(node x,node y){return x.w<y.w;}
vector<int>v[N];
void add(int x,int y){
    v[x].push_back(y);
    v[y].push_back(x);
}
void Add(int x,int y){
    x=id[x],y=id[y];
    add(x,y);
    A.add(x,y);
}
void dfs(int x,int fa){
    f[x]=fa;
    d[x]=d[fa]+1;
    for(int u:v[x]){
        if(u==fa)continue;
        dfs(u,x);
        sz[x]+=sz[u];
    }
}
void upd(int x,int y,int z){
    x=id[x],y=id[y];
    while(x!=y){
        if(d[x]<d[y])swap(x,y);
        mn[x]=min(mn[x],z),x=f[x];
    }
}
signed main(){
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1;i<=m;i++)scanf("%lld%lld%lld",&q[i].u,&q[i].v,&q[i].w);
    for(int i=1;i<=k;i++)scanf("%lld%lld",&qe[i].u,&qe[i].v);
    for(int i=1;i<=n;i++)scanf("%lld",p+i);
    A.init(n);
    for(int i=1;i<=k;i++)A.add(qe[i].u,qe[i].v);
    sort(q+1,q+1+m);
    for(int i=1;i<=m;i++)qn[i]=q[i];
    int tot=0;
    for(int i=1;i<=m;i++){
        if(!A.in(q[i].u,q[i].v)){
            A.add(q[i].u,q[i].v);
            q[++tot]=q[i];
        }
    }
    int TOT=0;
    A.init(n);
    for(int i=1;i<=tot;i++)A.add(q[i].u,q[i].v);
    for(int i=1;i<=m;i++){
        if(!A.in(qn[i].u,qn[i].v)){
            A.add(qn[i].u,qn[i].v);
            qn[++TOT]=qn[i];
        }
    }
    A.init(n);
    int cnt=0;
    for(int i=1;i<=tot;i++)A.add(q[i].u,q[i].v);
    for(int i=1;i<=n;i++)if(A.f[i]==i)id[i]=++cnt,SZ[cnt]=A.sz[i];
    for(int i=1;i<=n;i++)id[i]=id[A.getf(i)];
    int ans=0;
    for(int i=1;i<(1<<k);i++){
        int res=0,flag=0;
        for(int j=1;j<=cnt;j++)sz[j]=SZ[j];
        A.init(cnt);
        for(int j=1;j<=cnt;j++)v[j].clear(),mn[j]=inf;
        for(int j=1;j<=k;j++){
            if((i>>j-1)&1^1)continue;
            if(A.in(id[qe[j].u],id[qe[j].v])){flag=1;break;}
            Add(qe[j].u,qe[j].v);
        }
        if(flag)continue;
        int idx=0;
        for(int j=1;j<=TOT;j++){
            if(!A.in(id[qn[j].u],id[qn[j].v]))Add(qn[j].u,qn[j].v);
            else Q[++idx]=qn[j];
        }
        dfs(id[1],0);
        for(int j=1;j<=idx;j++){
            upd(Q[j].u,Q[j].v,Q[j].w);
        }
        for(int j=1;j<=k;j++){
            if((i>>j-1)&1^1)continue;
            int x=id[qe[j].u],y=id[qe[j].v];
            if(d[x]<d[y])swap(x,y);
            res+=mn[x]*sz[x];
        }
        ans=max(ans,res);
    }    
    printf("%lld",ans);
    return 0;
}