[APIO2013]道路费用

我不是女神ヾ 2022-01-12 10:47 215阅读 0赞

[\[APIO2013\]道路费用 ][APIO2013]

给一些边确定权值，再找MST，还要最大化，很麻烦

不妨枚举k中一个子集最终会在MST上，此基础上最大化每个边的权值（显然这样最优）

暴力：

2^k枚举S，把S中的边都先加进去。原图所有的边跑kruskal，得到MST

再对于没有在MST上的边，对(x,y)链上的S中的边有权值限制<=w，链上权值对w取min

O(2^k\*(mlogm+mk^2))

正解：

k<=20，每次跑一边全局的MST太不值得了。

假设Wki=-inf，即把S=全集都加进去，原图所有边跑kruskal，这个时候在MST上的边，一定无论如何都会在MST上了

不经过这k条边，可以缩点！

K+1个连通块编号为1~K+1

这样每次check变成了O(k^3)因为有k^2条原图的边

显然，这k^2条边不是必须的

Wki=inf，即直接用这些边跑MST，如果不在MST上的，无论如何都不会在了。并且不会影响S的边的min

所以，边、点剩下k个

O(mlogm+2\*k\*k^2)

// luogu-judger-enable-o2
    #include<bits/stdc++.h>
    #define reg register int
    #define il inline
    #define fi first
    #define se second
    #define mk(a,b) make_pair(a,b)
    #define numb (ch^'0')
    #define pb push_back
    #define solid const auto &
    #define enter cout<<endl
    using namespace std;
    typedef long long ll;
    template<class T>il void rd(T &x){
        char ch;x=0;bool fl=false;
        while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
        for(x=numb;isdigit(ch=getchar());x=x*10+numb);
        (fl==true)&&(x=-x);
    }
    template<class T>il void output(T x){
        if(x/10)output(x/10);putchar(x%10+'0');}
    template<class T>il void ot(T x){
        if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
    template<class T>il void prt(T a[],int st,int nd){
        for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
    
    namespace Miracle{
    const int N=1e5+5;
    const int M=3e5+5;
    const int K=30;
    const int inf=0x3f3f3f3f;
    int n,m,k;
    ll ans;
    struct node{
        int x,y,w;
        bool friend operator <(node a,node b){
            return a.w<b.w;        
        }
    }E[M],t[K],mao[K];
    struct edge{
        int nxt,to;
        int z;
    }e[2*N];
    int hd[N],cnt;
    void add(int x,int y,int z){
        e[++cnt].nxt=hd[x];
        e[cnt].to=y;e[cnt].z=z;
        hd[x]=cnt;
    }
    int be[N];
    int num;
    int tc;
    
    int gf[N];
    int fin(int x){
        return gf[x]==x?x:gf[x]=fin(gf[x]);
    }
    int has[N],tot;
    int fa[N];
    int dep[N];
    ll sum[K],val[K],wei[N];
    int big[K];
    int on[K];
    void dp(int x,int d){
        dep[x]=d;
        sum[x]=val[x];
        for(reg i=hd[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(y==fa[x]) continue;
            fa[y]=x;
            dp(y,d+1);
            sum[x]+=sum[y];
        }
    }
    ll che(){
        if(tot==0) return 0;
        for(reg i=1;i<=num;++i){
            gf[i]=i;
            hd[i]=0;
            big[i]=inf;
        }
        cnt=0;
        for(reg p=1;p<=tot;++p){
            int i=has[p];
            int x=mao[i].x,y=mao[i].y;
            int k1=fin(x),k2=fin(y);
            if(k1!=k2){
                gf[k1]=k2;
                add(x,y,0);add(y,x,0);
            }
        }
        for(reg i=1;i<=tc;++i){
            on[i]=0;
            int x=t[i].x,y=t[i].y;
            int k1=fin(x),k2=fin(y);
            if(k1!=k2){
                gf[k1]=k2;
                on[i]=1;
                add(x,y,0);add(y,x,0);
            }
        }
        fa[1]=0;dep[1]=0;
        dp(1,1);
        for(reg i=1;i<=tc;++i){
            if(!on[i]){
                int x=t[i].x,y=t[i].y;
                if(dep[x]<dep[y]) swap(x,y);
                while(dep[x]>dep[y]) big[x]=min(big[x],t[i].w),x=fa[x];
                while(x!=y){
                    big[x]=min(big[x],t[i].w);
                    big[y]=min(big[y],t[i].w);
                    x=fa[x],y=fa[y];
                }
            }
        }
        ll ret=0;
        for(reg p=1;p<=tot;++p){
            int i=has[p];
            int x=mao[i].x,y=mao[i].y;
            if(dep[x]<dep[y]) swap(x,y);
            ret+=(ll)big[x]*sum[x];
        }
        return ret;
    }
    void dfs(int x){
        if(x==k+1){
            ans=max(ans,che());
            return;
        }
        dfs(x+1);
        has[++tot]=x;
        dfs(x+1);
        has[tot--]=0;
    }
    
    void tarjan(int x){
        be[x]=num;
        val[num]+=wei[x];
        for(reg i=hd[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(be[y]||e[i].z) continue;
            tarjan(y);
        }
    }
    int main(){
        rd(n);rd(m);rd(k);
        for(reg i=1;i<=m;++i){
            rd(E[i].x);rd(E[i].y);rd(E[i].w);
        }
        for(reg i=1;i<=k;++i){
            rd(mao[i].x);rd(mao[i].y);
        }
        for(reg i=1;i<=n;++i){
            rd(wei[i]);
        }
        sort(E+1,E+m+1);
        for(reg i=1;i<=n;++i){
            gf[i]=i;
        }
        for(reg i=1;i<=k;++i){
            int x=mao[i].x,y=mao[i].y;
            int k1=fin(x),k2=fin(y);
            if(k1!=k2){
                gf[k1]=k2;
                add(x,y,1);add(y,x,1);
            }
        }
    
        for(reg i=1;i<=m;++i){
            int x=E[i].x,y=E[i].y;
            int k1=fin(x),k2=fin(y);
            if(k1!=k2){
                gf[k1]=k2;
                add(x,y,0);add(y,x,0);
            }
        }
        for(reg i=1;i<=n;++i){
            if(!be[i]){
                ++num;
                tarjan(i);
            }
        }
        memset(gf,0,sizeof gf);
        for(reg i=1;i<=num;++i){
            gf[i]=i;
        }
        for(reg i=1;i<=m;++i){
            int x=E[i].x,y=E[i].y;
            if(be[x]!=be[y]){
                x=be[x];y=be[y];
                int k1=fin(x),k2=fin(y);
                if(k1!=k2){
                    gf[k1]=k2;
                    ++tc;
                    t[tc].x=x;t[tc].y=y;
                    t[tc].w=E[i].w;
                }
            }
        }
        for(reg i=1;i<=k;++i){
            mao[i].x=be[mao[i].x];
            mao[i].y=be[mao[i].y];
        }
        memset(hd,0,sizeof hd);
        cnt=0;
        dfs(1);
        ot(ans);
        return 0;
    }
    
    }
    signed main(){
        Miracle::main();
        return 0;
    }
    
    /*
       Author: *Miracle*
    */

k很小，考虑暴力枚举，这样有了方向

每次MST太亏，考虑化简点、边

化简边数，找必须边和不可能边类似：[\[HNOI2010\]城市建设][HNOI2010]

转载于:https://www.cnblogs.com/Miracevin/p/10801012.html

[APIO2013]: https://www.luogu.org/problemnew/show/P3639
[HNOI2010]: https://www.cnblogs.com/Miracevin/p/10785638.html