多校第二場1003 hdu 5302 Connect the Graph(構造)

タイトルリンク:
クリックしてリンクを開く
テーマ:
図のいくつかの情報を与えます.0,1,2本の黒辺に連なる点の個数、0,1,2本の白辺に連なる点の個数を含む.このような図を作成します.
テーマ分析:
まず,a[i]をi本の白辺が連なる点の個数,b[i]をi本の黒辺が連なる点の個数とする.
したがって、a[1]とb[1]は奇数にすることはできないと結論しやすい.両辺が白辺ごとに寄与できる度数は2であるため、白辺の総度数は必ず偶数であり、度数が1の点の個数が奇数であれば、総度数は必ず奇数であり、白辺の総度数と矛盾する.
黒い辺は白い辺と同じだ.
チェーンを構築することによって、2つの度数が1の点とすべての度数が2の点を得ることができます.度数が1の点が1より小さいことはできません.つまり、最小値が2です.では、このチェーンを構築するのは合理的です.黒いエッジについては、重複エッジが存在しないため、重複エッジを作成するときに、重複エッジの発生を防止するために、重複エッジをマークする必要があります.
最後に残りの度数が1の辺を探して、2つの点の白い辺の隣接する辺を探して、黒い辺のパリティの点は辺をつなぎます.
最後に得られたこの図は題意を満たす構造である.
コードは次のとおりです.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#define MAX 1000007

using namespace std;

int t;
int a[5],b[5];
int d[MAX];

int main ( )
{
    scanf ( "%d" , &t );
    while ( t-- )
    {
        for ( int i = 0 ; i < 3 ; i++ )
            scanf ( "%d" , &a[i] );
        for ( int i = 0 ; i < 3 ; i++ )
            scanf ( "%d" , &b[i] );
        //       
        int sum = 0;
        for ( int i = 0 ; i < 3 ; i++ )
            sum += a[i];
        if ( (a[1]&1) || (b[1]&1) )
        {
            puts("-1");
            continue;
        }
        if ( sum == 4 )
        {
            puts("4
1 2 0
1 3 0
2 3 1
3 4 1");
            continue;
        }
        printf ( "%d
" , a[1]/2+a[2]+b[1]/2+b[2] );
        int t = 1;
        //            2，         1
        while ( a[2] != -1 )
        {
            printf ( "%d %d 0
" , t , t+1 );
            t++;
            a[2]--;
        }
        t++;
        //                  1  
        while ( a[1] != 2 )
        {
            printf ( "%d %d 0
" , t , t+1 );
            t += 2;
            a[1] -= 2;
        }
        int tt = 0;
        //         ,       ，             
        for ( int i = 1 ; i <= sum ; i += 2 )
            d[tt++] = i;
        for ( int i = 2 ; i <= sum ; i += 2 )
            d[tt++] = i;

        t = 0;
        //        2  
        while ( b[2] != -1 )
        {
            printf ( "%d %d 1
" ,
                    min ( d[t] , d[t+1] ) , max ( d[t] , d[t+1]));
            t++;
            b[2]--;
        }
        t++;
        //                
        while ( b[1]!= 2 )
        {
            printf ( "%d %d 1
", min(d[t],d[t+1] ), max ( d[t],d[t+1]));
            t += 2;
            b[1] -= 2;
        }
    }
}