【Codeforces Round #457 (Div. 2) C】Jamie and Interesting Graph

在这里输入题意

【题解】

找比n-1大的最小的素数x
1-2,2-3..(n-2)-(n-1)长度都为1
然后(n-1)-n长度为(x-(n-2))
然后其他边长度都设为x+1就好了。
这样就能满足题意了。

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int n,m,ma;

bool is(int x){

    if (x<2) return false;

    int len = sqrt(x);

    for (int i = 2;i <= len;i++){

        if (x%i==0)

            return false;

    }

    return true;

}

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

    cin >> n >> m;

    for (int i = n-1;;i++)

        if (is(i)){

            ma = i;

            break;

        }

    cout <<ma<<' '<<ma<<endl;

    for (int i = 1;i <= n-2;i++){

        cout <<i<<' '<<i+1<<" 1"<<endl;

    }

    cout <<n-1<<" "<<n<<" "<<ma-(n-2)<<endl;

    int now = n-1;

    for (int i = 1;i <= n &&now<m;i++)

        for (int j = i+1;j <= n && now <m;j++){

            if (j != (i+1)){

                cout <<i<<" "<<j<<" "<<ma+1<<endl;

                now++;

            }

        }

	return 0;

}

巴特西

【Codeforces Round #457 (Div. 2) C】Jamie and Interesting Graph

最新文章

热门文章