Processing math: 100%

原文作者:莉墨 lymoe

官方题解所有者:我

所以文章中的一些第一人称指的是 lymoe 不是我 qwq

另外在此说明了版权问题


Problem Link

题目灵感

当初其实是想考察一下 “树上全源最短路” 和 “二分图染色”,想了很久也没想出怎么出。

最后就把这两个算法合到一块,就出现了这个题。

原本这个题难度并不高(刚开始数据 n 最大为 1000(其实数据加强后,难度也不高 QAQ)),后来 WAAutoMaton 发现了一个 O(n) 的算法,于是这个题就稍微难了一点。

Part 0-题目分析

分析题目可以发现,我们可以建立一个新图,新图中的点和原图中的点一一对应。如果 dis(u,v)k 则在新图中把 u,v 相连。

那么新图中的任意一个 “环” 都对应一个满足题目条件的序列 a1,a2,a3,,am

而如果新图中存在奇环,则为 “无解”。

part 1-测试点 1~10 40 分

先用弗洛伊德算法求出全源最短路,建立新图。

我们知道不存在奇环的图为二分图。所以对新图进行二分图染色(或者用并查集判断二分图),若该图是二分图,则 “有解”,若该图不是二分图,则 “无解”。

part 2-测试点 15~20 64 分(40+24)

把弗洛伊德算法改用 dfs 求树上全源最短路即可。如果你嫌码量太小,使用 tarjan、树剖、倍增等求 lca 的方法求最短路也可。

part 3-测试点 11~14 16 分

对于这一部分和下一部分的分数,已经不需要建立新图了,但是为了方便证明,我们还会说到这个新图。

我们来考虑一下这个退化成链的部分。

通过在纸上手造几个数据,我们可以发现新图的一个性质:若新图上存在奇数环,则一定存在三元环。

那么怎么证明呢?

由于链上的环跟链上的点编号无关,不妨设这个链上的点从左往右编号依次为 1,2,3,,n 。(1,2之间连边,2,3 之间连边… 以此类推)

设这个链对应的新图存在奇环 a1,a2,,am ,且 m3

不妨设 a1 为奇环中编号最小的点,ax 为奇环中编号最大的点。

那么显而易见 dis(a1,ax)k 。(因为如果奇环中距离最远的两个点距离都小于 k 的话,则新图上一定不存在这个奇环)

假设奇环上不存在一点 aq 满足 dis(a1,aq)k and dis(a1,ax)k ,则

dis(a1,a2)k

dis(a2,ax)<k

dis(a2,a3)k,dis(a2,ax)<k

dis(a3,ax)k,dis(a1,a3)<k

以此类推,可以用数学归纳法证明(这里就省略数学归纳的过程),dis(a2p,ax)<kdis(a2p+1,a1)<k ,其中 pN 。那么可以发现,因为 dis(a2p,ax)<k ,所以无法构成包含 ax 的奇环。

故产生矛盾,则奇环上存在一点满足 dis(a1,aq)k and dis(a1,ax)k

则证明了存在奇数环就一定存在三元环。

那么接下来,我们可以猜测:若存在三元环,则存在包括 1 号点和 n 号点的三元环。

证明:

我们设三元环为 (a1,a2,a3)a1<a2<a3

dis(a1,a2)k,a11

dis(1,a2)k

dis(a2,a3)k,a3n

dis(a2,n)k

所以存在三元环 (1,a2,n) 满足条件 。

那么对于链的解法就显而易见了。我们只需要求一下前缀和,然后看看链上是否存在一点能与首尾构成三元环。

part 4-测试点 21~25 100 分

对于这部分分,我们可以采用类比法(类比 part 3)。

同理我们先来证明,若存在奇数环,则存在三元环。

首先我们找到奇环里距离最远的两个点 a1,ax

假设奇环上不存在一点 aq 满足 dis(a1,aq)k and dis(a1,ax)k ,则

dis(a1,a2)k

dis(a2,ax)<k

dis(a2,a3)k,dis(a2,ax)<k

dis(a3,ax)k,dis(a1,a3)<k

…(若比较难理解可以自行画图)

所以与 part 3 相同,因为 dis(a2p,ax)<k ,所以无法构成包含 ax 的奇环。

那么接下来,我们可以猜测:若存在三元环,则存在包括直径两个端点的三元环。

证明:

首先我们将树简化:

大写字母表示点,小写字母表示边,该简化图中边长可以为 0

AB 为树的直径, (D,F,G) 为直径外一三元环。

我们可以假设三元环上任意一点都不满足“到 A 的距离不小于 k 且到 B 的距离不小于 k ” 。

不妨设 (f+d)+l+b<k ,则

(f+d)+ck

b+l<c

a+l+c>a+l+b+la+b

dis(A,D)>dis(A,B) ,则 (A,B) 不为直径,产生矛盾。

所以三元环上存在一点满足 “到 A 的距离不小于 k 且到 B 的距离不小于 k ”。

那么正解的算法也就显而易见了,只需要先求树的直径,再看看是否存在一点到直径两端距离不小于 k

最后贴出 std:

#include<stdio.h>
#include<string.h>
#define MAXN 1000005
struct node
{
    int eh;
}V[MAXN];
struct edge
{
    int v;
    int to;
    int next;
}E[MAXN*2];
int tot;
int dis1[MAXN],dis2[MAXN];
void add_edge(int from,int to,int v)
{
    E[++tot]=(edge){v,to,V[from].eh};
    V[from].eh=tot;
}
void dfs(int i,int fa,int* dis)
{
    int p;
    for(p=V[i].eh;p;p=E[p].next)
    {
        if(E[p].to==fa) continue;
        dis[E[p].to]=dis[i]+E[p].v;
        dfs(E[p].to,i,dis);
    }
}
int main()
{
    int n,i,T,x,y,v,k,flag;
    scanf("%d",&T);
    while(T--)
    {
        memset(V,0,sizeof(V));
        memset(E,0,sizeof(E));
        tot=0;flag=1;
        scanf("%d%d",&n,&k);
        for(i=0;i<n-1;i++)
        {
            scanf("%d%d%d",&x,&y,&v);
            add_edge(x,y,v);
            add_edge(y,x,v);
        }
        dis1[1]=0;
        dfs(1,0,dis1);x=1;
        for(i=2;i<=n;i++)
        {
            if(dis1[i]>dis1[x]) x=i;
        }
        dis1[x]=0;
        dfs(x,0,dis1);y=x;
        for(i=1;i<=n;i++)
        {
            if(dis1[i]>dis1[y]) y=i;
        }
        dis2[y]=0;
        dfs(y,0,dis2);
        for(i=1;i<=n;i++)
        {
            if(dis1[i]>=k&&dis2[i]>=k) flag=0;
        }
        if(flag) printf("Yes\n");
        else printf("Baka Chino\n");
    }
    return 0;
} 
C++
分类: 文章

Shuchong

菜鸡书虫

1 条评论

Vegetable Chicken · 2021年1月26日 8:52 下午

orzorz 书虫太强了

发表回复

Avatar placeholder

您的邮箱地址不会被公开。 必填项已用 * 标注