首页 > 代码库 > CF 337D 求圆交

CF 337D 求圆交

2024-08-24 23:49:18   222人阅读

题目链接：http://codeforces.com/problemset/problem/337/D

 

题意：就是一棵树上，有一些点被来自东方的神秘力量影响的，力量影响范围是d，为可能的力量源有几个。

 

思路：相当于是找到距离这m的点的距离都不小于d的点的个数。

 

先从任意一个点一次dfs，找到m个点中距离最远的点，标记为max1，在以max1开始，dfs一遍，从数组d1记录各个点的距离，找到距离最远的点max2，再从max2开始跑一遍dfs，用d2记录距离。遍历所有点，到max1和max2的距离都小于d的点就成立。

//以上是题解讲的，但是我不懂为什么要先从任意一个点一次dfs，找到m个点中距离最远的点，再从这个点开始DFS。

//我写了一个直接找两个最远的点，求圆交的WA了。等我搞懂了再来补充。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;

int n,m,d;
int a[maxn],d1[maxn],d2[maxn];
int vit[maxn];
int head[maxn],k;

struct Edge
{
    int v;
    int next;
} edge[maxn<<1];

void init()
{
    k=0;
    memset(head,-1,sizeof(head));
    memset(d1,0,sizeof(d1));
    memset(d2,0,sizeof(d2));
}

void addedge(int u,int v)
{
    edge[k].v=v;
    edge[k].next=head[u];
    head[u]=k++;

    edge[k].v=u;
    edge[k].next=head[v];
    head[v]=k++;
}

void dfs1(int u,int t)
{
    for(int i=head[u]; i!=-1; i=edge[i].next)
    {
        int v=edge[i].v;
        if(vit[v]==0)
        {
            vit[v]=1;
            d1[v]=t+1;
            dfs1(v,t+1);
        }
    }
}

void dfs2(int u,int t)
{
    for(int i=head[u]; i!=-1; i=edge[i].next)
    {
        int v=edge[i].v;
        if(vit[v]==0)
        {
            vit[v]=1;
            d2[v]=t+1;
            dfs2(v,t+1);
        }
    }
}

int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d%d",&n,&m,&d)==3)
    {
        init();
        for(int i=1; i<=m; i++) scanf("%d",&a[i]);
        int x,y;
        for(int i=1; i<n; i++)
        {
            scanf("%d%d",&x,&y);
            addedge(x,y);
        }

        memset(vit,0,sizeof(vit));
        vit[1]=1;
        dfs2(1,0);

        int dd=-INF,max1,max2;
        for(int i=1; i<=m; i++)
            if(d2[a[i]]>dd) dd=d2[a[i]],max1=a[i];

        memset(vit,0,sizeof(vit));
        vit[max1]=1;
        dfs1(max1,0);

        dd=-INF;
        for(int i=1; i<=m; i++)
            if(d1[a[i]]>dd) dd=d1[a[i]],max2=a[i];

        memset(d2,0,sizeof(d2));
        memset(vit,0,sizeof(vit));
        vit[max2]=1;
        dfs2(max2,0);

        int ans=0;
        for(int i=1; i<=n; i++)
            if(d1[i]<=d && d2[i]<=d)
                ans++;
        printf("%d\n",ans);
    }
    return 0;
}

 

CF 337D 求圆交


联系
我们