c/c++语言开发共享cf550D. Regular Bridge(构造)

题意 给出一个$k$,构造一个无向图,使得每个点的度数为$k$,且存在一个桥 Sol 神仙题 一篇写的非常好的博客:http://www.cnblogs.com/mangoyang/p/9302269.html 我简单的来说一下构造过程 首先$n$是偶数的时候无解 奇数的时候:我们拿出两个点作为桥 …


题意

给出一个$k$,构造一个无向图,使得每个点的度数为$k$,且存在一个桥

sol

神仙题

一篇写的非常好的博客:https://www.cnblogs.com/mangoyang/p/9302269.html

我简单的来说一下构造过程

首先$n$是偶数的时候无解

奇数的时候:我们拿出两个点作为桥

先构建一条桥边,对于两个端点分别做同样操作:

新建$k1$个点,每个点向端点连边

再新建$k−1$个点,每个点向相邻的点连边

对于两层点形成的二分图,两两之间连边

/*  */  #include<iostream>  #include<cstdio>  #include<cstring>  #include<algorithm>  #include<map>  #include<vector>  #include<set>  #include<queue>  #include<cmath>  //#include<ext/pb_ds/assoc_container.hpp>  //#include<ext/pb_ds/hash_policy.hpp>  #define pair pair<int, int>  #define mp(x, y) make_pair(x, y)  #define fi first  #define se second  //#define int long long   #define ll long long   #define ull unsigned long long   #define rg register   #define pt(x) printf("%d ", x);  //#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? eof : *p1++)  //char buf[(1 << 22)], *p1 = buf, *p2 = buf;  //char obuf[1<<24], *o = obuf;  //void print(int x) {if(x > 9) print(x / 10); *o++ = x % 10 + '0';}  //#define os  *o++ = ' ';  using namespace std;  //using namespace __gnu_pbds;  const int maxn = 1e6 + 10, inf = 1e9 + 10, mod = 1e9 + 7;  const double eps = 1e-9;  inline int read() {      char c = getchar(); int x = 0, f = 1;      while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}      while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();      return x * f;  }  int k, n, m;  void build(int t) {      for(int i = t + 1; i <= t + k - 1; i++)          printf("%d %dn", t, i);      for(int i = t + 1; i <= t + k - 1; i++)          for(int j = t + k ; j <= 2 * k + t - 2; j++)              printf("%d %dn", i, j);      for(int i = k + t; i <= 2 * k + t - 2; i++)          if(((t & 1) && (!(i & 1))) || ((!(t & 1)) && (i & 1))) printf("%d %dn", i, i + 1);  }  main() {      k = read();      if(!(k & 1)) {puts("no"); return 0;}      puts("yes");      n = (2 * (k - 1) + 1) * 2, m = n * k / 2;      printf("%d %dn", n, m);      printf("%d %dn", 1, n / 2 + 1);      build(1);       build(n / 2 + 1);      return 0;  }  /*  2 2 1  1 1  2 1 1  */

 

www.ctvol.com true Article c/c++语言开发共享cf550D. Regular Bridge(构造)

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。

ctvol管理联系方式QQ:251552304

本文章地址:https://www.ctvol.com/c-cdevelopment/608231.html

(0)
上一篇 2021年5月15日 上午3:52
下一篇 2021年5月15日 上午3:55

精彩推荐