ZOJ - Summer 2018 - Contest 1 by SBconscious - Problems - 1001: Saber

简介: ZOJ - Summer 2018 - Contest 1 by SBconscious - Problems - 1001: Saber

Saber


Time Limit: 2 Seconds      Memory Limit: 65536 KB      Score: 1


Saber is a Class in the Holy Grail War. This Class is regarded as one of the most powerful Class.


Saber is a tree-lover. She loves all kinds of trees. One day, she suddenly comes up with a curious problem. She wants to know that in the path between x and y, whether it exists that when we choose three different edges i,j,k, the length of these three edges can build a triangle. Now she wants you to solve this problem.


Input


There are multiple test cases. The first line of input contains an integer T(T ≤ 5), indicating the number of test cases. For each test case:


The first line contains one integer N(1 ≤ N ≤ 100000), indicating the number of tree’s vertices. In the following N-1 lines, there are three integers x, y, w (1 ≤ w ≤ 1000000000), indicating an edge weighted w between x and y.


In the following line also contains one integer Q(1 ≤ Q ≤ 100000), indicating the number of queries. In the following Q lines, there are two integers x, y, indicating a query between x and y.


Output


For each test case output ‘Case #i:’ in the first line, i equals to the case number. Then for every query output ‘Yes’ or ‘No’ in one line.


Sample Input


/

2
5
1 2 5
1 3 20
2 4 30
4 5 15
2
3 4
3 5
5
1 4 32
2 3 100
3 5 45
4 5 60
2
1 4
1 3

Sample Output

Case #1:
No
Yes
Case #2:
No
Yes

解题思路

1、因为题目说明了是树,所以保证给出的数据是一定能通的。2、存在的路径中找到是否存在三条边构成三角形,此时的路径是两点的唯一路径,不包括其他死胡同的边(哪怕是相通的)。3、斐波那契数列与三角形的关联(破 TLE)。

AC 代码(每次 DFS 版)

#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=100000+100;
struct node
{
    int e,w;
    //node(int e,int w):e(e),w(w){} // 推荐这种写法,用到时,无需再定义声明
};
vector<node> ve[maxn];
int vis[maxn], num[60];
int n,m,s,e,flag,found;
void init()
{
    for(int i=0;i<=maxn;i++)
//        ve[i].clear();
        vector<node>().swap(ve[i]); // 这种写法比 clear() 更彻底清除
    m=n-1;
    mem(vis,0);
}
int ok(int a,int b,int c)
{
    return a+b>c;
}
void dfs(int s,int step)
{
    // 50的标记是来自于斐波那契数列上限46就达到了此题目中的最大值
    // 所以顶峰是45时,再无论加一条边就肯定能找到构成的三角形的三条边
    if(step>50 || found) return;
    if(s==e)
    {
        found=1;
        if(step>50)
        {
            flag=1;
            return;
        }
        sort(num,num+step);
        int a,b,c;
        for(int i=2;i<step;i++) // 判断是否可以构成三角形
        {
            a=num[i-2], b=num[i-1], c=num[i];
            if(ok(a,b,c))
            {
                flag=1;
                return;
            }
        }
        return;
    }
    for(int i=0;i<ve[s].size();i++)
    {
        if(!vis[ve[s][i].e])
        {
            vis[ve[s][i].e]=1;
            num[step]=ve[s][i].w;
            dfs(ve[s][i].e,step+1);
            vis[ve[s][i].e]=0;
        }
    }
    return;
}
int main()
{
    int T,kase=0; scanf("%d",&T);
    while(T-- && ~scanf("%d",&n))
    {
        init();
        int u,v,w,q;
        node nd1,nd2;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            nd1.e=v; nd1.w=w;
            nd2.e=u; nd2.w=w;
            ve[u].push_back(nd1);
            ve[v].push_back(nd2);
        }
        scanf("%d",&q);
        printf("Case #%d:\n",++kase);
        for(int i=0;i<q;i++)
        {
            scanf("%d%d",&s,&e);
            found=flag=0;
            vis[s]=1; // 别忘记一开始就已经经过的这个点s
            dfs(s,0);
            vis[s]=0;
            // found == 0 是因为在到终点的途中就已经超过了阈值,所以就可以马上return,此时的found一定等于0
            puts(!found || flag?"Yes":"No");
        }
    }
    return 0;
}

AC 代码(公共祖先版,仅需一次 DFS)

#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=100100;
int n,tp;
int dep[maxn], dis[maxn], fa[maxn], head[maxn], num[maxn];
struct edge
{
    int to,w,nx;
}eds[2*maxn]; // *2 是因为是无向图
void init()
{
    tp=0;
    mem(head,-1);
}
void addEdge(int u, int v, int w)
{
    eds[tp].to=v;
    eds[tp].w=w;
    eds[tp].nx=head[u];
    head[u]=tp++;
}
void dfs(int u, int f, int w, int d)
{
    int v;
    fa[u]=f;
    dis[u]=w;
    dep[u]=d;
    for(int i=head[u];i!=-1;i=eds[i].nx)
    {
        v=eds[i].to;
        w=eds[i].w;
        if(v!=f) dfs(v,u,w,d+1); // v!=f 避免从 1->2 又反过来 2->1 的情况
    }
}
int main()
{
    int T,kase=0; scanf("%d",&T);
    while(T-- && ~scanf("%d",&n))
    {
        init();
        int u,v,w;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            addEdge(u,v,w);
            addEdge(v,u,w);
        }
        dfs(1,0,0,1);
        int q,len; scanf("%d",&q);
        printf("Case #%d:\n",++kase);
        for(int i=0;i<q;i++)
        {
            scanf("%d%d",&u,&v);
            len=0;
            while(dep[u]>dep[v]&&len<50) num[len++]=dis[u], u=fa[u]; // 在公共祖先的一侧且 u 在 v 的后面
            while(dep[v]>dep[u]&&len<50) num[len++]=dis[v], v=fa[v]; // 在公共祖先的一侧且 v 在 u 的后面
            while(u!=v&&len<50) num[len++]=dis[v], v=fa[v], num[len++]=dis[u], u=fa[u]; // 在公共祖先的两侧
            sort(num,num+len);
            int ok=0;
            for(int j=0;j<len-2;j++)
            {
                if(num[j]+num[j+1]>num[j+2])
                {
                    ok=1; break;
                }
            }
            puts(ok?"Yes":"No");
        }
    }
    return 0;
}
目录
相关文章
|
2天前
|
弹性计算 人工智能 安全
云上十五年——「弹性计算十五周年」系列客户故事(第二期)
阿里云弹性计算十五年深耕,以第九代ECS g9i实例引领算力革新。携手海尔三翼鸟、小鹏汽车、微帧科技等企业,实现性能跃升与成本优化,赋能AI、物联网、智能驾驶等前沿场景,共绘云端增长新图景。
|
8天前
|
存储 弹性计算 人工智能
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
2025年9月24日,阿里云弹性计算团队多位产品、技术专家及服务器团队技术专家共同在【2025云栖大会】现场带来了《通用计算产品发布与行业实践》的专场论坛,本论坛聚焦弹性计算多款通用算力产品发布。同时,ECS云服务器安全能力、资源售卖模式、计算AI助手等用户体验关键环节也宣布升级,让用云更简单、更智能。海尔三翼鸟云服务负责人刘建锋先生作为特邀嘉宾,莅临现场分享了关于阿里云ECS g9i推动AIoT平台的场景落地实践。
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
|
7天前
|
人工智能 自然语言处理 自动驾驶
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
|
6天前
|
云安全 人工智能 自然语言处理
阿里云x硅基流动:AI安全护栏助力构建可信模型生态
阿里云AI安全护栏:大模型的“智能过滤系统”。
|
7天前
|
编解码 自然语言处理 文字识别
Qwen3-VL再添丁!4B/8B Dense模型开源,更轻量,仍强大
凌晨,Qwen3-VL系列再添新成员——Dense架构的Qwen3-VL-8B、Qwen3-VL-4B 模型,本地部署友好,并完整保留了Qwen3-VL的全部表现,评测指标表现优秀。
618 7
Qwen3-VL再添丁!4B/8B Dense模型开源,更轻量,仍强大
|
10天前
|
存储 机器学习/深度学习 人工智能
大模型微调技术:LoRA原理与实践
本文深入解析大语言模型微调中的关键技术——低秩自适应(LoRA)。通过分析全参数微调的计算瓶颈,详细阐述LoRA的数学原理、实现机制和优势特点。文章包含完整的PyTorch实现代码、性能对比实验以及实际应用场景,为开发者提供高效微调大模型的实践指南。
734 2