专栏文章

题解：P3323 [SDOI2015] 旅行计划

mmiller2014
P3323题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minfmcqz
此快照首次捕获于
2025/12/02 01:37
3 个月前
此快照最后确认于
2025/12/02 01:37
3 个月前
查看原文
题目传送门

1.思路分析

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

2.具体做法

2.1

k=2k=2
枚举起点 ii 与终点 jj ，连接就输出Y，否则输出N。

2.2

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

2.3

k=4k=4
先枚举起点 ii 与终点 jj ，再枚举点 ii 连接的所有除点 jj 以外的点 kk ，然后枚举点 jj 连接的所有除点 ii 与点 kk 以外的点 ll 。如果四者连通就输出Y，否则输出N。

2.4

k=5k=5
先枚举起点 ii 与终点 jj ，再枚举点 ii 连接的所有除点 jj 以外的点 kk ，然后枚举点 jj 连接的所有除点 ii 与点 kk 以外的点 ll ，接着枚举点 kk 连接的所有除点 ii 、点 jj 与点 ll 以外的点 oo 。如果五者连通就输出Y，否则输出N。

2.5

k=6k=6
先枚举起点 ii 与终点 jj ，再枚举点 ii 连接的所有除点 jj 以外的点 kk ，然后枚举点 jj 连接的所有除点 ii 与点 kk 以外的点 ll ，接着枚举点 kk 连接的所有除点 ii 、点 jj 与点 ll 以外的点 oo ，之后枚举点 ll 连接的所有除点 ii 、点 jj 、点 kk 与点 oo 以外的点 pp 。如果六者连通就输出Y，否则输出N。

2.6

k=7k=7 先枚举起点 ii 与终点 jj ，再枚举点 ii 连接的所有除点 jj 以外的点 kk ，然后枚举点 jj 连接的所有除点 ii 与点 kk 以外的点 ll ，接着枚举点 kk 连接的所有除点 ii 、点 jj 与点 ll 以外的点 oo ，之后枚举点 ll 连接的所有除点 ii 、点 jj 、点 kk 与点 oo 以外的点 pp ，最后枚举点 oo 连接的所有除点 ii 、点 jj 、点 kk 、点 ll 与点 pp 以外的点 qq 。如果六者连通就输出Y，否则输出N。

3 代码

3.1

直接循环即可。
CPP
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

注意如果满足条件直接退出。
CPP
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

马蜂有点差，不喜勿喷。
CPP
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

同上。
CPP
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

同上。
CPP
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

同上。
CPP
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

CPP
#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;
}
已做防伪处理，请勿复制！！！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...