Codeforces Round #745 (Div. 2) B. Diameter of Graph

Codeforces Round #745 (Div. 2)  B. Diameter of Graph

Codeforces Round #745 (Div. 2)  B. Diameter of Graph


场上思路:发现存在两种特殊情况:边数最小的菊花树和边数最大的完全图。但由于理解错一般无向图直径的定义,不会处理介于菊花图与完全图之间的情况。此外,对于完全图直径为1和菊花图直径为2的性质理解的也不够深刻。

改进:对于题目定义的新概念要思考,同时要注意积累特殊情况的性质(异或和、菊花图等)。

Codeforces Round #745 (Div. 2)  B. Diameter of Graph

 

#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        ll n,m,k;
        scanf("%lld%lld%lld",&n,&m,&k);
        //特殊情况判断 
        
        if(n==1){
            if(m==0&&k>=2){
                printf("YES\n");
                continue;
            }else{
                printf("NO\n");
                continue;
            }
        }
        if(m<n-1||m>(n*(n-1))/2||k<=2){//严格小于k-1,即<=k-2,1<=k-2,k=3 
            //完全不可能满足条件(边数和直径要求) 
            printf("NO\n");
            continue;
        }else{
            //恰好构成菊花图 
            if(m==n-1&&k>=4){//4-1=3>2
                printf("YES\n");
                continue;
            }
            //一部分完全,一部分为菊花图 
            else if(m>n-1&&m<(n*(n-1)/2)){//不完全菊花图 
                if(k>=4){
                    printf("YES\n");
                    continue;
                }else{
                    printf("NO\n"); 
                    continue;
                }
            }
            else if(m==(n*(n-1)/2)&&k>=3){//完全图 
                printf("YES\n");
                continue;
            }else{
                printf("NO\n"); 
                continue;
            }
            
        }
    }
    return 0;
}

 

上一篇:图学习学术速递[2021/10/14]


下一篇:iText7解套(三)列表中文中文序号