提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

CodeForces - 916C 思维

Codeforces 思维
2023-09-27 14:26:03 时间

题意：给你n，m，表示n个顶点和m条边，让你构造一个图。

要求

1.1->n最短路为素数

2.最小生成树边权和为prime

3.没有重边

4.边大小[1,1e9]。

(题目给定m>n-1) 

 

题解：

你可以先构造一个  最短路==最小生成树权值和==素数  ，然后剩下的边保证不重复的前提下赋一个大的值就行

 

具体看代码：

 1 #include<stdio.h>
 2 int main()
 3 {
 4     int n,m;
 5     scanf("%d%d",&n,&m);
 6     int prim=100003;
 7     printf("%d %d\n",prim,prim);
 8     printf("1 2 %d\n",prim-(n-2));
 9     for(int i=2;i<n;++i)
10         printf("%d %d 1\n",i,i+1);
11     m=m-(n-1);
12     for(int i=1;i<=n;++i)
13     {
14         for(int j=i+2;j<=n;++j)
15         {
16             if(!m) break;
17             printf("%d %d %d\n",i,j,2*prim);
18             m--;
19         }
20     }
21     return 0;
22 }

 

相关文章