1 条题解

  • 0
    @ 2021-10-30 8:35:29

    题意

    已知一个图,你需要完成下面两个任务中的一个。

    • 找到一条长度大于等于 n2\lceil \frac{n}{2} \rceil 的链。

    • 选出若干个点对,使得至少包括 n2\lceil \frac{n}{2} \rceil 个点,且不能包含相同的点,且对于任意两个点对 (a,b),(c,d)(a,b),(c,d),需要满足 a,b,c,d{a,b,c,d} 的子图中的边小于等于 22

    题解

    利用 dfsdfs 树的性质。

    如果有一个点的深度大于等于 n2\lceil \frac{n}{2} \rceil,那么直接满足第一个条件。

    否则利用 dfsdfs 树的性质,一个点的子树之间没有边,因此每个点对都选深度相同的两个点,这样最多浪费 n2\lceil \frac{n}{2}\rceil 个点,满足条件。

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=5e5+5;
    int dep[N],f[N],n,m,_;
    vector<int> e[N],vec[N];
    vector<pair<int,int> > ans;
    void dfs(int x,int fa){
        dep[x]=dep[fa]+1;
        f[x]=fa;
        for(int y:e[x]){
            if(dep[y])continue;
            dfs(y,x);
        }
    }
    void work1(int x){//第一个条件
        puts("PATH");
        printf("%d\n",dep[x]);
        for(;x;x=f[x])printf("%d ",x);
        puts("");
    }
    void work2(){//第二个条件
        puts("PAIRING");
        for(int i=1;i<=n;i++)vec[i].clear();
        for(int i=1;i<=n;i++)vec[dep[i]].push_back(i);
        ans.clear();
        for(int i=1;i<=n;i++){
            for(int j=1;j<vec[i].size();j+=2){
                ans.emplace_back(vec[i][j],vec[i][j-1]);
            }
        }
        printf("%d\n",ans.size());
        for(auto i:ans)printf("%d %d\n",i.first,i.second);
    }
    int main() {
        scanf("%d",&_);
        while(_--){
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++)e[i].clear(),dep[i]=0,f[i]=0;
            for(int i=1;i<=m;i++){
                int x,y;
                scanf("%d%d",&x,&y);
                e[x].push_back(y);
                e[y].push_back(x);
            }
            dfs(1,0);
            int ff=0;
            for(int i=1;i<=n;i++){
                if(dep[i]>=(n+1)/2){
                    work1(i);
                    ff=1;
                    break;
                }
            }
            if(!ff)work2();
        }
        return 0;
    }
    
    • 1

    信息

    ID
    807
    时间
    3000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    5
    已通过
    3
    上传者