xindoo is
always here

Codeforces Round #192 (Div. 2) (330B) B.Road Construction


题意:

     要在N个城市之间修建道路,使得任意两个城市都可以到达,而且不超过两条路,还有,有些城市之间是不能修建道路的。

思路:

    要将N个城市全部相连,刚开始以为是最小生成树的问题,其实就是一道简单的题目。  要求两个城市之间不超过两条道路,那么所有的城市应该是连在一个点上的,至于这个点就很好找了,只要找到一个没有和其他点有道路限制的即可。

//cf 192 B
#include <stdio.h>
#include <string.h>

char map[1005][1005];

int main()
{
    int n, m;
    while (scanf("%d %d", &n, &m) != EOF)
    {
        int s, e;
        memset(map, 0, sizeof(map));
        for (int i = 1; i <= m; i++)
        {
            scanf("%d %d", &s, &e);
            map[s][e] = 1;
            map[e][s] = 1;
        }
        int x;
        for (int i = 1; i <= n; i++)
        {
            int flag = 1;
            for (int j = 1; j <= n; j++)
            {
                if (map[i][j])
                {
                    flag = 0;
                    break;
                }
            }
            if (flag)
            {
                x = i;
                break;
            }
        }
        printf("%d\n", n-1);
        for (int i = 1; i <= n; i++)
        {
            if (x == i)
                continue;
            else
                printf("%d %d\n", x, i);
        }
    }
    return 0;
}


打赏
未经允许不得转载:XINDOO » Codeforces Round #192 (Div. 2) (330B) B.Road Construction
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏