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--;
            }
        }
    }

}


目录
相关文章
|
Java
hdu1016 Prime Ring Problem【素数环问题(经典dfs)】
hdu1016 Prime Ring Problem【素数环问题(经典dfs)】
48 0
hdoj 1028/poj 2704 Pascal's Travels(记忆化搜索||dp)
有个小球,只能向右边或下边滚动,而且它下一步滚动的步数是它在当前点上的数字,如果是0表示进入一个死胡同。求它从左上角到右下角到路径数目。 注意, 题目给了提示了,要用64位的整数。
37 0
|
vr&ar
CF482B. Interesting Array(线段树)
CF482B. Interesting Array(线段树)
63 1
CF711D-Directed Roads(组合数学 dfs找环)
CF711D-Directed Roads(组合数学 dfs找环)
84 0
CF711D-Directed Roads(组合数学 dfs找环)
Codeforces Round #748 (Div. 3) E. Gardener and Tree(拓扑排序)
Codeforces Round #748 (Div. 3) E. Gardener and Tree(拓扑排序)
92 0
CF 1156D. 0-1-Tree(树形DP)
CF 1156D. 0-1-Tree(树形DP)
102 0
HDU7050.Link with Limit(有向图tarjan找环)
HDU7050.Link with Limit(有向图tarjan找环)
139 0
|
Java
HDOJ/HDU 1297 Children’s Queue(推导~大数)
HDOJ/HDU 1297 Children’s Queue(推导~大数)
139 0