WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #192 Div2 B "Road Construction"

問題

http://codeforces.com/contest/330/problem/B

ある国にはn個の都市がある。初め、都市を結ぶ道路はない。ある日、王様は2つの都市を結ぶ道路をいくつか建設しようと決めた。道路はどちらの方向にも渡ることができるものである。彼は任意の都市から他の任意の都市へ、多くとも2つの道路を渡っていく事が出来るよう、道路を建設することを望んでいた。あなたはまた、この都市間に道路を建設してはならないという、m個の都市のペアの情報が与えられる。

あなたの仕事は王様の上記の望みを守りつつも、建設する道路の数をなるべく少なくすることである。その道路の数を出力せよ。

制約

1 <= n <= 1000
0 <= m <= n / 2




考えた事

他のどんな都市とも道路を繋ぐ事を禁止されていない都市があるのなら、その都市を中心として、スター型に道路を作ればよい。そのような都市がない可能性もある。それは禁止情報の都市がまったく重複していないときである(n=6ならば1-2 3-4 5-6など)。こーゆー時は、適当に禁止ペアを選んで、それを離して次のように道路を建設すればよい。
f:id:Ekaing:20130728132717j:plain




ソースコード

int a[550], b[550];
bool ok[1050];

int main() {
    int N, M;
    cin >> N >> M;
    memset( ok, true, sizeof(ok) );
    for( int i = 0; i < M; i++ ){
        cin >> a[i] >> b[i];
        ok[a[i]] = ok[b[i]] = false;
    }

    // スターの中心を見つける
    int center = -1;
    for( int i = 1; i <= N; i++ ){
        if( ok[i] ){
            center = i;
            break;
        }
    }

    // スター型
    if( center != -1 ){
        cout << (N - 1) << endl;
        for( int i = 1; i <= N; i++ ){
            if( center != i ){
                printf( "%d %d\n", center, i );
            }
        }
    }
    // 2つの都市を離す型
    else{
        int one = a[0];
        int two = b[0];
        cout << ( (N-2) * 2 ) << endl;
        for( int i = 1; i <= N; i++ ){
            if( one != i && two != i ){
                printf( "%d %d\n", one, i );
                printf( "%d %d\n", two, i );
            }
        }
    }
}