CF350E Wrong Floyd

洛谷题目链接

前言：

这题其实真的不难

回归正题:

我们首先要明白$floyd$的思想，相信你都来做这道水题了，肯定不陌生，简单的手玩后，我们可以发现：

只要有任意一个点只跟非标记点相连的话，是更新不出它到另外的标记点的距离的，并且题目中$k>=2$是很关键的，光说不清楚，举个例子：

$n=5,m=4,k=2$，标记点为$1,5$时：

只需要如下连：

$1-2,1-3,1-4,4-5$，就能够$hack$，为什么呢，我们看到题目中是以标记点为中间点来更新最短距离

那么以$1$为标记点时，能更新出：$2-3,2-4,3-4$的最短距离，而以$5$为标记点时,什么都不能更新出，所以$1-5$的最短距离就不能算出来

那么总结一下连边的规律：

$1$、随便选一个点（下面代码选的是随机的标记点），只跟非标记点相连

$2$、把所有未加入图中的点加入，向除了上面选的点的点连边

$3$、如果边数不满$m$的话，想怎么连就怎么连$qwq$，前提还是不和上面的点相连

那么输出$-1$的情况呢？？

$1$、当所有点都是标记点的时候，其实就是一个完整的$floyd$，难道你能$hack$吗，（逃）

$2$、当$m$很大，让你不能够腾出一个点只跟非标记点相连的时候，输出$-1$，具体的话是$(n-1)*(n-2)/2+n-k$，为什么呢？其实是我们要保证一个点只跟非标记点连边，那么连的边数就是$n-k$，那么其他的点随便怎么连，但是最多就是个完全图，也就是$(n-1)*(n-2)/2$了，相加即可

接下来是美滋滋的代码时间~~~

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#define N 307

using namespace std;

int n,m,k,it,it1,line;

bool g[N][N],mark[N],vis[N];

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    if((k==n)||(m>(n-1)*(n-2)/2+n-k))

    {

        printf("-1");

        return 0;

    }

    for(int i=1;i<=k;++i)

    {

        int in;

        scanf("%d",&in);

        mark[in]=1;

        it=in;

    }

    vis[it]=1;

    for(int i=1;i<=n;++i)

        g[i][i]=1;

    for(int i=1;i<=n;++i)

    {

        if(i==it||mark[i])

            continue;

        printf("%d %d\n",i,it);

        ++line;

        vis[i]=1;

        g[i][it]=g[it][i]=1;

        it1=i;

        if(line==m)

            return 0;

    }

    for(int i=1;i<=n;++i)

    {

        if(line==m)

            return 0;

        if(vis[i])

            continue;

        printf("%d %d\n",i,it1);

        ++line;

        g[i][it1]=g[it1][i]=1;

        vis[i]=1;

    }

    for(int i=1;i<=n;++i)

    {

        if(line==m)

            return 0;

        if(i==it)

            continue;

        for(int j=1;j<=n;++j)

        {

            if(j==it||g[i][j])

                continue;

            if(line==m)

                return 0;

            printf("%d %d\n",i,j);

            g[i][j]=g[j][i]=1;

            ++line;

        }

    }

    return 0;

}

巴特西

CF350E Wrong Floyd

最新文章

热门文章