开发者社区> jxy> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

CF 203 div2 E. Wrong Floyd 图论

简介:
+关注继续查看

    题目中只选取k个点更新,因此只要保证有一个点只连到非k点即可

    注意:题目要求连通图!!比赛的时候没看到,WA了,只要改下输出顺序即可保证联通。

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int vis[305];
int main()
{
    int n,k,m;
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        int i,t,j;
        memset(vis,0,sizeof(vis));
        for(i=0;i<k;i++)
        {
            scanf("%d",&t);
            vis[t]=1;
        }
        int Max=n-k+(n-1)*(n-2)/2;
        if(k==n||m>Max)puts("-1");
        else
        {
            int f=1,last;
            while(!vis[f])f++;
            for(i=1;i<=n&&m;i++)
            {
                if(vis[i])continue;
                printf("%d %d\n",f,i); //先输出一组保证错误
                last=i;
                m--;
                break;
            }
            for(i=1;i<=n&&m;i++)
            {
                if(i==f)continue;
                for(j=i+1;j<=n&&m;j++)
                {
                    if(j==f)continue;
                    printf("%d %d\n",i,j); //保证联通
                    m--;
                }
            }
            for(i=last+1;i<=n&&m;i++)
            {
                if(vis[i])continue;
                printf("%d %d\n",f,i); 
                m--;
            }
        }
    }

}


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【DCIC2022】科技金融子赛道验证码识别0.65+ baseline
刚开始做OCR比赛,周末补了下相关知识,主要参考内容来自【官方】十分钟掌握PaddleOCR使用,不过目前分数不是很高,0.65+,主要存在过拟合问题,大家可以再修改配置或者模型再微调下,这里主要给大家提供一个流水线和科普下CRNN的相关原理
37 0
使用easydrag实现可拖动的DIV弹出框
最近在工作中遇到了jquery的easydrag插件,我有一种相见恨晚的赶脚!easydrag极大的方法我们实现div弹框这个功能,使我爱不释手!<br>在没遇到easydrag插件之前,想实现一个弹出框并不是一件轻而易举的事情!<br>人们常说没有不劳而获的事情,但在编码的世界中却不是这样。更多的开源框架方面了我们,也毒害了我们!<br><p style="margin-top:15px;
1599 0
C# System.Drawing.Region类的方法使用图解
本实例使用两个矩形A和B来演示System.Drawing.Region类的各方法的功能。 源码下载:CSharp_Region类的方法使用图解 绘制两个矩形 获取目标矩形与此Region不相交的部分 获取此Region与目标矩形不相交的部分 获取两个矩形的交集 获取两个矩形的并集 获取两个矩形的并集中不相交的部分 将此 System.
893 0
最短路径—Dijkstra算法和Floyd算法【转】
本文来自博客园的文章:http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html   Dijkstra算法 1.定义概览 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。
1077 0
+关注
jxy
176
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载