2015年6月6日 星期六

[CF 550D] Regular Bridge

作法:

這題我的構造跟官方解的一樣,這裡就寫一下我是怎麼想到的。
因為要有橋,所以大概可以想到把橋的兩邊分開構。因為每個點的度都要是$k$,所以當把橋拔掉後,其中一個連通分量裡每個點的度會長的像:$k-1,k,...,k$。因此當$k$是偶數的時候無解,因為度總和必須是偶數。當$k$奇數時,$k=1$題目構完了,如果$k=3$,先試著構一個度為$2,3,3,3,3$的圖(因為$3$個$3$時奇偶性不對,$3$個以下時點太少),假設五個點分別為$ABCDE$,那麼先連$BD,CE$,剩下的只要再找一個圈就可以了,也就是連上$AB,BC,CD,DE,EA$,這樣就構完$k=3$的情形了。仔細觀察可以發現,其實他就是一個$k+2$接完全圖,拔掉$A$和其中兩個點($C,D$)連的邊,然後把剩下的點($B,E$)兩兩配對,把他們之間的邊拔掉所得來的,並且這個構造容易推廣到$k$是更大的奇數的情形,於是在把兩個這樣的圖用橋連起來就做完了。

code :



#include<bits/stdc++.h>
using namespace std;
const int maxn=200+10 ;
 
bool G[maxn][maxn] ;
main()
{
    int k ; scanf("%d",&k) ;
    if(k%2==0){printf("NO\n") ; return 0 ;}
    printf("YES\n") ;
    if(k==1){printf("2 1\n1 2\n") ; return 0 ;}
 
    int n=2*(k+2) ;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
        G[i][j]=1 ;
    for(int r=0;r<=k+2;r+=k+2)
    {
        for(int i=2;i<=k;i+=2)
            G[r+i][r+i+1]=G[r+i+1][r+i]=0 ;
        G[r+1][r+k+1]=G[r+k+1][r+1]=0 ;
        G[r+1][r+k+2]=G[r+k+2][r+1]=0 ;
    }
    for(int i=1;i<=k+2;i++) for(int j=k+3;j<=n;j++)
        G[i][j]=G[j][i]=0 ;
    G[1][k+3]=1 ;
 
    int m=0 ;
    for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)
        if(G[i][j]) m++ ;
    printf("%d %d\n",n,m) ;
    for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)
        if(G[i][j]) printf("%d %d\n",i,j) ;
 
}
 

沒有留言:

張貼留言