原题与此题
原题是一道神仙不可做题, 两者区别在于, 原题不能有重边和自环.
然而, 这题可以有重边...
于是这题就变成了一道大水题.
此题的解法
考虑如何构造.
对于 \(n\le10^4\) 的情况:
对于 \(n>10^4\) 的情况:
边上的权值表示边数.
代码
- #pragma GCC optimize(2)
- #include<bits/stdc++.h>
- #define Tp template<typename Ty>
- #define Ts template<typename Ty,typename... Ar>
- #define Reg register
- #define RI Reg int
- #define Con const
- #define CI Con int&
- #define I inline
- #define W while
- using namespace std;
- int n;
- int main()
- {
- freopen("road.in","r",stdin),freopen("road.out","w",stdout);
- RI i;if(scanf("%d",&n),n<=10000)// 对于 n<=10000 的情况
- {
- for(printf("2 %d\n",n),i=1;i<=n;++i) puts("1 2");// 暴力建边
- return 0;
- }
- printf("4 %d\n",10001+n/10000+n%10000);// 对于 n>10000 的情况
- for(i=1;i<=10000;++i) puts("1 2");puts("1 3");// 分两组建边
- for(i=1;i<=n/10000;++i) puts("2 4");for(i=1;i<=n%10000;++i) puts("3 4");
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3136187.html