方案问题（vjudge里的）

有一个n个节点的树，有k个关键节点，问最多删去多少条边可以使得每个点到离自己最近的关键节点的距离小于等于d，要求输出一种删边方案。

很显然我们可以让删掉之后的每个联通块内只有一个关键节点。这样是最优的，那么我们从所有关键节点开始同时bfs，遇上连接两个不同关键节点控制区域的边就将这个边删去，显然可以得到最好的答案

#include
#include
#include
#include
#include<string>
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define _f(i,a,b)  for(register int i=a;i<=b;++i)

#define f_(i,a,b)  for(register int i=a;i>=b;--i)

#define ll long long

#define chu printf


using namespace std;
inline int re()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
const int WR=1001000;int INF=0x7f7f7f7f;
int ne,h[300004];
struct edge
{
    int to,nt,w;
 } e[600004];
 void add(int u,int v,int w)
 {
     e[++ne].to=v,e[ne].nt=h[u],h[u]=ne;e[ne].w=w;
 }
 int dis[300004],pit[300004];
 int n,k,d,p[300004];
 queue<int>q;
 vector<int>ans;
/*
给出一颗树（n点，n-1边，可以互相到达）
求删去最多的边，使得任意一个点可以到达指定的某几个点（在d的距离之内） 
*/
int main()
{
//    freopen("makeans.txt","r",stdin);
//    freopen("fire.out","w",stdout);
    ne=0;
    while(!q.empty())q.pop();
    memset(pit,0,sizeof(pit));
    memset(h,0,sizeof(h));
    n=re(),k=re(),d=re();
    _f(i,1,n)dis[i]=INF;
    for(int i=1;i<=k;i++)
    {
        p[i]=re();
        q.push(p[i]);
        dis[p[i]]=0;
    }
    for(int i=1;i)
    {
        int u=re(),v=re();
        add(u,v,i);add(v,u,i);
    }

    while(!q.empty())
    {
            //chu("dfdsf\n");
        int x=q.front();q.pop();
    //    chu("%d\n",x);
        for(int i=h[x];i;i=e[i].nt)
        {
            if(dis[e[i].to]==INF)
            {
                dis[e[i].to]=dis[x]+1;
                pit[e[i].w]=1;
                q.push(e[i].to);
            //    chu("in:%d\n",e[i].to);
            }
        }
    }
    ans.clear();
    for(int i=1;i)
    {
        if(!pit[i])ans.push_back(i);
    }
    chu("%d\n",ans.size());
    int siz=ans.size();
    _f(i,0,siz-1)chu("%d ",ans[i]);
    if(ans.size())puts("");
    
    return 0;
}
/*
树：每个节点只唯一 
从警察局出发遍历每一个节点
如果在距离之内能到达的点，有另一个边就删掉，
如果这个点也是关键节点
把这个边也删掉

6 2 4
1 6
1 2
2 3
3 4
4 5
5 6
 
 
 6 3 2
1 5 6
1 2
1 3
1 4
1 5
5 6

*/

图论

方案问题（vjudge里的）

相关

图论---网络流

数的重心(图论深搜)

电子科技大学《图论及其应用》复习总结--第七章图的着色

电子科技大学2017年《图论及其应用》试卷及答案

图论算法遍历基础

图论算法与模型（训练指南题库）

图论中的初始值

图论算法-最小生成树

LeetCode题解-07（简单图论）

图论学习笔记（二）

关于树（图论初步）

专题训练3-图论 - B - Learning Languages（并查集）

标签