欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Global Round 4 Problem-D. Prime Graph

程序员文章站 2022-06-04 09:24:49
...

D. Prime Graph: http://codeforces.com/contest/1178/problem/D

题意:

有1-n, n个点,然后给这些点之间连上线,要求:

1. 无向图,没有重边和自环

2. n不必是素数

3. 边的总数是一个素数

4. 每个点的度必须是一个素数

输入一个n, 输出符合这些条件的边的个数和边。

分析:

有这样一个规律,设当前素数为x,下一个素数为y,则 y < x + x/2
所以先先把12345....n连成一个环,然后在这个环内连到边数为n的下一个素数,如果n就是素数,那么就不需要在环内连边了。

Codeforces Global Round 4 Problem-D. Prime Graph

这样就有11条边,且每个点的度也都为素数。

注意:虽然与样例的答案不一样但也是对的,而且题目说的很清楚,不止一种情况,任意输出一种即可。

code:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10000;

int prime[MAXN];
void init()     // 初始化先筛选出素数
{
    prime[0] = prime[1] = 1;
    int n = sqrt(MAXN+1);
    for(int i=2; i<n; i++)
    {
        if(!prime[i])
        {
            for(int j=i+i; j<MAXN; j+=i)
                prime[j] = 1;
        }
    }
}
int graph[1000+7][1000+7];  // 存图

int main()
{
    init();
    int n;
    while(scanf("%d", &n) != EOF)
    {
        memset(graph, 0, sizeof(graph));
        int ans = 0;
        for(int i=1; i<n; i++)
        {
            graph[i][i+1] = 1;  // 存的时候只存一个就可以了,方便输出边。
            ans ++;   // 记录边的个数
        }
        graph[1][n] = 1; 
        ans ++;
        int i = 1, j = n-1; // 连环内的边,确保每个点的度不超过3
        while(j - i > 0)
        {
            if(!prime[ans]) // 边数为素数就可以终止了
                break;
            graph[i][j] = 1;
            ans ++;
            i++, j--;
        }
        // if(n%2 ==1 && !prime[ans])
        // {
        //     graph[(n+1)/2][n-1] = 1;
        //     ans ++;
        // }

        printf("%d\n", ans);
        for(int i=0; i<1007; i++)
        {
            for(int j=0; j<1007; j++)
            {
                if(graph[i][j])
                    printf("%d %d\n", i, j);
            }
        }
    }


    return 0;
}

 

相关标签: codeforces