题解：P3323 [SDOI2015] 旅行计划

miller2014 · 2025-11-01 20:18:40 · 题解

题目传送门

1.思路分析

我们发现 2\le k\le7 ，所以只需针对 k 不同的值进行分析即可。

2.具体做法

2.1

枚举起点 i 与终点 j ，连接就输出Y，否则输出N。

2.2

先枚举起点 i 与终点 j ，再枚举起点连接的所有除终点以外的点 k 。如果三者连通就输出Y，否则输出N。

2.3

先枚举起点 i 与终点 j ，再枚举点 i 连接的所有除点 j 以外的点 k ，然后枚举点 j 连接的所有除点 i 与点 k 以外的点 l 。如果四者连通就输出Y，否则输出N。

2.4

先枚举起点 i 与终点 j ，再枚举点 i 连接的所有除点 j 以外的点 k ，然后枚举点 j 连接的所有除点 i 与点 k 以外的点 l ，接着枚举点 k 连接的所有除点 i 、点 j 与点 l 以外的点 o 。如果五者连通就输出Y，否则输出N。

2.5

先枚举起点 i 与终点 j ，再枚举点 i 连接的所有除点 j 以外的点 k ，然后枚举点 j 连接的所有除点 i 与点 k 以外的点 l ，接着枚举点 k 连接的所有除点 i 、点 j 与点 l 以外的点 o ，之后枚举点 l 连接的所有除点 i 、点 j 、点 k 与点 o 以外的点 p 。如果六者连通就输出Y，否则输出N。

2.6

先枚举起点 i 与终点 j ，再枚举点 i 连接的所有除点 j 以外的点 k ，然后枚举点 j 连接的所有除点 i 与点 k 以外的点 l ，接着枚举点 k 连接的所有除点 i 、点 j 与点 l 以外的点 o ，之后枚举点 l 连接的所有除点 i 、点 j 、点 k 与点 o 以外的点 p ，最后枚举点 o 连接的所有除点 i 、点 j 、点 k 、点 l 与点 p 以外的点 q 。如果六者连通就输出Y，否则输出N。

3 代码

3.1

直接循环即可。

void s2()
{
    for(int i=1;i<=n;i++)
        for(int j:e[i])
            b[i][j]=b[j][i]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)cout<<(b[i][j]?'Y':'N');
        cout<<"\n";
    }
}

3.2

注意如果满足条件直接退出。

void s3()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
        {
            flag=0;
            for(int k:e[i])
            {
                if(k!=i&&k!=j&&a[k][j])
                    b[i][j]=b[j][i]=flag=1;
                if(flag)break;
            }
        }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)cout<<(b[i][j]?'Y':'N');
        cout<<"\n";
    }
}

3.3

马蜂有点差，不喜勿喷。

void s4()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            flag=0;
            for(int k:e[i])
            {
                if(k!=i&&k!=j)
                {
                    for(int l:e[j])
                    {
                        if(l!=i&&l!=j&&l!=k&&a[k][l])
                        {
                            b[i][j]=b[j][i]=flag=1;
                        }
                        if(flag)
                        {
                            break;
                        }
                    }
                }
                if(flag)
                {
                    break;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)cout<<(b[i][j]?'Y':'N');
        cout<<"\n";
    }
}

3.4

同上。

void s5()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            flag=0;
            for(int k:e[i])
            {
                if(k!=i&&k!=j)
                {
                    for(int l:e[j])
                    {
                        if(l!=i&&l!=j&&l!=k)
                        {
                            for(int o:e[k])
                            {
                                if(o!=i&&o!=j&&o!=k&&o!=l&&a[o][l])
                                {
                                    b[i][j]=b[j][i]=flag=1;
                                }
                                if(flag)
                                {
                                    break;
                                }
                            }
                        }
                        if(flag)
                        {
                            break;
                        }
                    }
                }
                if(flag)
                {
                    break;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)cout<<(b[i][j]?'Y':'N');
        cout<<"\n";
    }
}

3.5

同上。

void s6()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            flag=0;
            for(int k:e[i])
            {
                if(k!=i&&k!=j)
                {
                    for(int l:e[j])
                    {
                        if(l!=i&&l!=j&&l!=k)
                        {
                            for(int o:e[k])
                            {
                                if(o!=i&&o!=j&&o!=k&&o!=l)
                                {
                                    for(int p:e[o])
                                    {
                                        if(p!=i&&p!=j&&p!=k&&p!=l&&p!=o&&a[p][l])
                                        {
                                            b[i][j]=b[j][i]=flag=1;
                                        }
                                        if(flag)
                                        {
                                            break;
                                        }
                                    }
                                }
                                if(flag)
                                {
                                    break;
                                }
                            }
                        }
                        if(flag)
                        {
                            break;
                        }
                    }
                }
                if(flag)
                {
                    break;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)cout<<(b[i][j]?'Y':'N');
        cout<<"\n";
    }
}

3.6

同上。

void s7()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            flag=0;
            for(int k:e[i])
            {
                if(k!=i&&k!=j)
                {
                    for(int l:e[j])
                    {
                        if(l!=i&&l!=j&&l!=k)
                        {
                            for(int o:e[k])
                            {
                                if(o!=i&&o!=j&&o!=k&&o!=l)
                                {
                                    for(int p:e[l])
                                    {
                                        if(p!=i&&p!=j&&p!=k&&p!=l&&p!=o)
                                        {
                                            for(int q:e[o])
                                            {
                                                if(q!=i&&q!=j&&q!=k&&q!=l&&q!=o&&q!=p&&a[p][q])
                                                {
                                                    b[i][j]=b[j][i]=flag=1;
                                                }
                                                if(flag)
                                                {
                                                    break;
                                                }
                                            }
                                        }
                                        if(flag)
                                        {
                                            break;
                                        }
                                    }
                                }
                                if(flag)
                                {
                                    break;
                                }
                            }
                        }
                        if(flag)
                        {
                            break;
                        }
                    }
                }
                if(flag)
                {
                    break;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)cout<<(b[i][j]?'Y':'N');
        cout<<"\n";
    }
}

3.7 ACcode

#include<bits/stdc++.h>
using namespace std;
int _,n,m,k,u,v,flag,a[1005][1005],b[1005][1005];
vector<int> e[1005];
void s2()
{
    for(int i=1;i<=n;i++)
        for(int j:e[i])
            b[i][j]=b[j][i]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)cout<<(b[i][j]?'Y':'N');
        cout<<"\n";
    }
}
void s3()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
        {
            flag=0;
            for(int k:e[i])
            {
                if(k!=i&&k!=j&&a[k][j])
                    b[i][j]=b[j][i]=flag=1;
                if(flag)break;
            }
        }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)cout<<(b[i][j]?'Y':'N');
        cout<<"\n";
    }
}
void s4()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            flag=0;
            for(int k:e[i])
            {
                if(k!=i&&k!=j)
                {
                    for(int l:e[j])
                    {
                        if(l!=i&&l!=j&&l!=k&&a[k][l])
                        {
                            b[i][j]=b[j][i]=flag=1;
                        }
                        if(flag)
                        {
                            break;
                        }
                    }
                }
                if(flag)
                {
                    break;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)cout<<(b[i][j]?'Y':'N');
        cout<<"\n";
    }
}
void s5()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            flag=0;
            for(int k:e[i])
            {
                if(k!=i&&k!=j)
                {
                    for(int l:e[j])
                    {
                        if(l!=i&&l!=j&&l!=k)
                        {
                            for(int o:e[k])
                            {
                                if(o!=i&&o!=j&&o!=k&&o!=l&&a[o][l])
                                {
                                    b[i][j]=b[j][i]=flag=1;
                                }
                                if(flag)
                                {
                                    break;
                                }
                            }
                        }
                        if(flag)
                        {
                            break;
                        }
                    }
                }
                if(flag)
                {
                    break;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)cout<<(b[i][j]?'Y':'N');
        cout<<"\n";
    }
}
void s6()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            flag=0;
            for(int k:e[i])
            {
                if(k!=i&&k!=j)
                {
                    for(int l:e[j])
                    {
                        if(l!=i&&l!=j&&l!=k)
                        {
                            for(int o:e[k])
                            {
                                if(o!=i&&o!=j&&o!=k&&o!=l)
                                {
                                    for(int p:e[o])
                                    {
                                        if(p!=i&&p!=j&&p!=k&&p!=l&&p!=o&&a[p][l])
                                        {
                                            b[i][j]=b[j][i]=flag=1;
                                        }
                                        if(flag)
                                        {
                                            break;
                                        }
                                    }
                                }
                                if(flag)
                                {
                                    break;
                                }
                            }
                        }
                        if(flag)
                        {
                            break;
                        }
                    }
                }
                if(flag)
                {
                    break;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)cout<<(b[i][j]?'N':'Y');
        cout<<"\n";
    }
}
void s7()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            flag=0;
            for(int k:e[i])
            {
                if(k!=i&&k!=j)
                {
                    for(int l:e[j])
                    {
                        if(l!=i&&l!=j&&l!=k)
                        {
                            for(int o:e[k])
                            {
                                if(o!=i&&o!=j&&o!=k&&o!=l)
                                {
                                    for(int p:e[l])
                                    {
                                        if(p!=i&&p!=j&&p!=k&&p!=l&&p!=o)
                                        {
                                            for(int q:e[o])
                                            {
                                                if(q!=i&&q!=j&&q!=k&&q!=l&&q!=o&&q!=p&&a[p][q])
                                                {
                                                    b[i][j]=b[j][i]=flag=1;
                                                }
                                                if(flag)
                                                {
                                                    break;
                                                }
                                            }
                                        }
                                        if(flag)
                                        {
                                            break;
                                        }
                                    }
                                }
                                if(flag)
                                {
                                    break;
                                }
                            }
                        }
                        if(flag)
                        {
                            break;
                        }
                    }
                }
                if(flag)
                {
                    break;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)cout<<(b[i][j]?'N':'Y');
        cout<<"\n";
    }
}
int main()
{
    cin>>_;
    while(--_)
    {
        for(int i=1;i<=n;i++)e[i].clear();
        memset(b,0,sizeof(b));
        memset(a,0,sizeof(a));
        cin>>n>>m>>k;
        while(--m)
        {
            cin>>u>>v;
            a[u][v]=a[v][u]=1,e[u].push_back(v),e[v].push_back(u);
        }
        switch(k)
        {
            case 2:
                s2();
                break;
            case 3:
                s3();
                break;
            case 4:
                s4();
                break;
            case 5:
                s5();
                break;
            case 6:
                s6();
                break;
            case 7:
                s7();
                break;
        }
    }
    return 0;
}

已做防伪处理，请勿复制！！！