UOJ61. 【UR #5】怎样更有力气

题目链接

Statement

给定一棵 \(n\) 点树 \(T\) 和 \(m\) 个操作 v u w ：

在 \(T\) 中 \(u,v\) 的最短路上所有点里面选出若干对（可以不选，可以重复），在每一对之间加边，花费为 \(w\) .
有 \(p\) 个限制 t a b ，表示第 \(t\) 次不能在 \(a,b\) 之间加边，保证 \(a,b\) 在 \(u,v\) 的路径上且无重复。

求所有加的边形成 \(n\) 点连通图的最小代价。 \(n,m,p\leq 3e5\) .

Solution

一开始看错题了

一个显然的想法是，把每一天按照 \(w\) 升序，然后每次尽可能多地合并连通块。

有一个显然的性质： 对于第 \(i\) 天，设当天有 \(num\) 个限制，如果 \(dis(u,v)>num\) ，那么这一条路径上的所有点之间都能连通，且必须连通

Proof

长度是 \(dis(u,v)\) ，点数就是 \(dis(u,v)+1\) .既然 \(dis(u,v)\) 比 \(num\) 大，那么就算一个点包揽了 \(num\) 个限制，也至少能向一个点连边，这样就一定可以使得路径上所有点连通。而由于我们是将每一次操作按 \(w\) 升序的，所以这一次将它连边一定不会比后面再做劣，因此这种情况下，第 \(i\) 次做完之后一定是 \(path(u,v)\) 全部连通。

那么对于满足这个性质的情况，直接连就好了，反正连完就是同一个连通块。（网上题解为啥说的是能直接连边啊……虽然是等价的）

现在来考虑 \(dis(u,v)\leq num\) 的情况。

首先，对于 \(t\) 的所有限制，建立一个子图 \(g\) ，并暴力把 \(u\to v\) 路径上的所有点都存下来，设为 \(path[]\) .令 \(t\) 的限制个数为 \(k\) .

然后，选取一个度数最小的点 \(x\) ，将路径上的点集分成两类：\(V_1\) 中的点在限制子图中和 \(x\) 相邻，\(V_2\) 反之。

显然，对于 \(V_2\) 的点，直接和 \(x\) 连边就好了。

对于 \(V_1\) 中的点 \(y\) ，如果 \(deg[y]<|V_2|\) （这里的度数是和 \(V_2\) 的度数），那么至少能和 \(V_2\) 中一个点连边，直接加边即可。复杂度 \(\mathcal{O}(\sum_y deg[y])=\mathcal{O}(k)\) .

否则，暴力枚举 \(V_1\) 中的点，尝试两两连边。由于度数最小所以 \(deg[x]\) 是根号级别的，复杂度 \(\mathcal{O}(k)\) .

所以总体复杂度是 \(\mathcal{O}(n\log n)\) （同级复杂度），瓶颈在于排序。

Code

//Author: RingweEH

const int N=3e5+10;

struct Date

{

    int u,v,w,t;

    bool operator < ( const Date &tmp ) const { return w<tmp.w; }

}a[N];

struct DSU

{

    int fa[N];

    int find( int x ) { return x==fa[x] ? x : fa[x]=find(fa[x]); }

    DSU() { for ( int i=1; i<=N-10; i++ )   fa[i]=i; }

}D1,D2;

int n,m,k,fa[N],dep[N];

ll ans=0;

bool vis[N];

vector<Date> restr[N];

vector<int> g[N];

stack<Date> sta;

bool Check_Length( int u,int v,int num )        //判断dis(u,v)的长度和限制个数的大小关系

{

    while ( num-- )

    {

        if ( dep[u]>dep[v] ) swap( u,v );

        v=fa[v];

        if ( u==v ) return 0;

    }

    return 1;

}

void Merge( int u,int v,int w )

{

    u=D2.find( u ); v=D2.find( v );

    if ( u!=v ) D2.fa[v]=u,ans+=w;

}

void Add( int u,int v )

{

    g[u].push_back( v ); g[v].push_back( u );

    Date tmp; tmp.u=u; tmp.v=v; tmp.w=tmp.t=0; sta.push( tmp );

}

void Clear( int u=0,int v=0 )

{

    while ( !sta.empty() )

    {

        u=sta.top().u; v=sta.top().v; sta.pop();

        g[u].clear(); g[v].clear();

    }

}

int path[N],lenth;

void Get_Path( int u,int v )

{

    lenth=0; bool fl=0;

    do

    {

        fl=(u==v);

        if ( dep[u]>dep[v] ) swap( u,v );

        path[++lenth]=v; v=fa[v];

    } while ( !fl );

}

int main()

{

    n=read(); m=read(); k=read();

    for ( int i=2; i<=n; i++ )

        fa[i]=read(),dep[i]=dep[fa[i]]+1;

    for ( int i=1; i<=m; i++ )

        a[i].u=read(),a[i].v=read(),a[i].w=read(),a[i].t=i;

    for ( int i=1,u,v,t; i<=k; i++ )

        t=read(),u=read(),v=read(),restr[t].push_back( (Date){u,v,0,0} );

    sort( a+1,a+1+m );

    for ( int i=1; i<=m; i++ )

    {

        int u=a[i].u,v=a[i].v,w=a[i].w,t=a[i].t;

        if ( Check_Length(u,v,restr[t].size()) )        //满足性质

        {

            u=D1.find( u ); v=D1.find( v );

            while ( u^v )

            {

                if ( dep[u]>dep[v] ) swap( u,v );

                Merge( v,fa[v],w ); D1.fa[v]=fa[v]; v=D1.find( v );

            }

        }

        else

        {

            for ( Date j : restr[t] )

                Add( j.u,j.v );     //对于限制建子图

            Get_Path( u,v ); int mn=path[1];

            for ( int j=2; j<=lenth; j++ )      //找度数最小的点

                if ( g[path[j]].size()<g[mn].size() ) mn=path[j];

            for ( int j : g[mn] )       //标记相邻点

                vis[j]=1;

            for ( int j=1; j<=lenth; j++ )    //x & V2

                if ( !vis[path[j]] ) Merge( mn,path[j],w );

            for ( int j : g[mn] )

            {

                int sum=0;

                for ( int p : g[j] )

                    sum+=vis[p];

                if ( g[j].size()-sum-1<lenth-g[mn].size()-1 ) Merge( j,mn,w );

                //deg[y]<|V2|

            }

            for ( int j : g[mn] )

                vis[j]=0;

            for ( int j : g[mn] )

            {

                for ( int p : g[j] )

                    vis[p]=1;

                for ( int p : g[mn] )       //V1中两两尝试连边

                    if ( !vis[p] ) Merge( j,p,w );

                for ( int p : g[j] )

                    vis[p]=0;

            }

            Clear();

        }

    }

    printf( "%lld\n",ans );

    return 0;

}

巴特西

UOJ61. 【UR #5】怎样更有力气

Statement

Solution

Code

最新文章

热门文章