当前位置: 代码迷 >> 综合 >> Codeforces Round #306 (Div. 2) D. Regular Bridge (构造)
  详细解决方案

Codeforces Round #306 (Div. 2) D. Regular Bridge (构造)

热度:28   发布时间:2023-12-17 03:37:31.0

题意:

构造一个无向图,让每个点的度数为k,并且至少一个桥(可能无法构造出)

思路:

首先,我们能够想到,如果一个无向图含有一个桥,在割断桥以后,如果左边和右边相等,那么是不影响结果的,所以我们只要想办法构造一边就好了。

那么对于连着桥的那个端点,它还需要k-1条边,那么我们就暂时在加k-1个点,我们发现,这样是肯定无法满足的,那么我们加一个点,发现之前的k-1个点虽然满足了,可是这个新加的点无法满足,那么我们再加一个点,并且让这个点和k-1个点和刚刚加的点相连,就发现,我新加的两个点满足了,可是之前的k-1个点无法满足了。

如果我们此时这k-1个点之间没有相连,对于一个点,还需要连k-3的度数,如果我们让两个点与其他的k-3个点相连,这样就剩下k-3个点的度数不满足,且需要的度数为k-5,此刻我们就发现,我们把问题从k-1个点且每个都需要k-3个度数,变成了k-3个点且每个都需要k-5个度数,这样的话就能进行慢慢递推了,而且这个规则只对k-1为偶数的时候适用.

错误及反思:

代码:

#include<bits/stdc++.h>
using namespace std;
int main()
{int k;scanf("%d",&k);if(k==1)printf("YES\n2 1\n1 2\n");else if(k%2){printf("YES\n");vector<pair<int,int> > ans;ans.push_back({
   1,2});for(int i=0;i<k-1;i++){ans.push_back({
   1,i+3});ans.push_back({
   2,i+3});}for(int i=0;i<k-1;i++)ans.push_back({i+3,2+k});for(int i=0;i<k-1;i+=2)for(int j=i+2;j<k-1;j++){ans.push_back({i+1+2,j+2+1});ans.push_back({i+1+3,j+2+1});}ans.push_back({k+2,k+3});ans.push_back({
   4+k-1+k-1+2-1,4+k-1+k-1+2});for(int i=0;i<k-1;i++){ans.push_back({k-1+2+2+i+1,4+k-1+k-1+2-1});ans.push_back({k-1+2+2+i+1,4+k-1+k-1+2});}for(int i=0;i<k-1;i++)ans.push_back({k-1+2+2,k-1+2+2+i+1});for(int i=0;i<k-1;i+=2)for(int j=i+2;j<k-1;j++){ans.push_back({k-1+4+i+1,k-1+4+j+1});ans.push_back({k-1+4+i+2,k-1+4+j+1});}printf("%d %d\n",2*(k-1)+2+4,ans.size());for(int i=0;i<ans.size();i++)printf("%d %d\n",ans[i].first,ans[i].second);}else printf("NO\n");
}
  相关解决方案