Codeforces Round #408 (Div. 2) D. Police Stations（最小生成树+构造）

传送门

题意

n个点有n-1条边相连，其中有k个特殊点，要求：

删去尽可能多的边使得剩余的点距特殊点的距离不超过d

输出删去的边数和index

分析

比赛的时候想不清楚，看了别人的题解

一道将1个联通块转化为k个树的题目，考虑上界，应该是k-1条边，这k-1条边是原图中连接树与树的边，那么我们操作如下：

1.将特殊点i染色为i，放入队列

2.做一次bfs，对每个点相邻的点染色并判断

3.遍历边，如果边的两点不同色，则输出边的index

trick

代码

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <ctime>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <string>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <vector>

#include <bitset>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

#define cpy(a,b) memcpy(a,b,sizeof(b))

#pragma comment(linker, "/STACK:102400000,102400000")

inline void read(int &x){x=0; char ch=getchar();while(ch<'0') ch=getchar();while(ch>='0'){x=x*10+ch-48; ch=getchar();}}

int n,k,d,u,v;

vector<int>vec[300300];

vector<pair<int,int> >edg;

int f[300300],color[300300],dis[300300];

int cnt;

queue<int>q;

void bfs()

{

    while(!q.empty())

    {

        int u=q.front();q.pop();

        if(dis[u]==d) continue;

        R(i,0,vec[u].size())

        {

            int v=vec[u][i];

            if(!color[v])

            {

                color[v]=color[u];

                dis[v]=dis[u]+1;

                q.push(v);

            }

        }

    }

}

int main()

{

    scanf("%d %d %d",&n,&k,&d);

    F(i,1,k)

    {

        int x;

        scanf("%d",&x);

        f[x]=1;

    }

    F(i,1,n-1)

    {

        scanf("%d %d",&u,&v);

        edg.push_back(make_pair(u,v));

        vec[u].push_back(v);

        vec[v].push_back(u);

    }

    cnt=0;

    F(i,1,n)if(f[i])

    {

        q.push(i);

        color[i]=i;

        cnt++;

    }

    bfs();

    printf("%d\n",cnt-1);

    int now=0;

    //F(i,1,n) printf("color[%d]=%d\n",i,color[i]);

    R(i,0,n-1)

    {

        int u=edg[i].first,v=edg[i].second;

        if(color[u]!=color[v])

        {

            ++now;

            printf("%d%c",i+1,(now==(k-1))?'\n':' ');

        }

    }

    return 0;

}

巴特西

Codeforces Round #408 (Div. 2) D. Police Stations（最小生成树+构造）

传送门

题意

分析

trick

代码

最新文章

热门文章