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 圖論