1002      技术社区[云栖]

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

}

最后更新：2017-04-03 15:22:09

  上一篇： URAL 1132 二次剩余

  下一篇： poj 1021 2D-Nim 图论