zoj 3732 그래프 재 구성 (구조)

2699 단어
예비 지식: Havel - Hakimi 정리
먼저 HavelHakimi 알고리즘 은 해 가 있 는 지 판단 합 니 다.다 해 를 판단 하 는 상황 에 대해 다시 한번 HavelHakimi, sort (p + i, p + n) 정렬 후 i 에서 i + 1, i + 2... i + p [i]. d 로 연 결 될 때 i + p [i]. d 와 i + p [i]. d + 1 의 남 은 도수 가 같다 면 이 두 점 이 남 은 그림 의 위 치 를 교환 하면 두 개의 다른 그림 을 얻 을 수 있 습 니 다.
구덩이: 변수 가 0 일 때 도 두 개의 빈 줄 을 출력 해 야 합 니 다. 처음에는 첫 번 째 출력 이 인쇄 오류 인 줄 알 았 는데...
#include<algorithm>
#include<iostream>
#include<cstdio>
#define REP(i, n) for(int i=0; i<n; i++)
using namespace std;

const int maxn = 111;
const int maxm = maxn*maxn;
int n, tot;
pair<int, int> e1[maxm], e2[maxm];
struct Node
{
    int d, id;
    bool operator < (const Node& rhs) const
    {
        return d > rhs.d;
    }
}p[2][maxn];

void print(pair<int, int> *e)
{
    printf("%d %d
", n, tot); REP(i, tot) printf("%d%c", e[i].first, i == tot-1 ? '
' : ' '); REP(i, tot) printf("%d%c", e[i].second, i == tot-1 ? '
' : ' '); if(tot == 0) printf("

"); } bool solve(Node *p, pair<int, int> *e) { int cnt = 0; REP(i, n-1) { sort(p+i, p+n); if(p[i].d+i > n-1) return false; for(int j=i+1; j <= p[i].d+i; j++) { if(--p[j].d < 0) return false; e[cnt++] = make_pair(p[i].id+1, p[j].id+1); } } return p[n-1].d == 0; } bool gao(Node *p, pair<int, int> *e) { int cnt = 0, ret = 0; REP(i, n-1) { sort(p+i, p+n); int tmp = p[i].d + i; if(tmp < n-1 && p[tmp].d == p[tmp+1].d && p[tmp].d != 0) { ret = 1; swap(p[tmp].id, p[tmp+1].id); } for(int j=i+1; j<=tmp; j++) p[j].d--, e[cnt++] = make_pair(p[i].id+1, p[j].id+1); } return ret; } int main() { while(~scanf("%d", &n)) { tot = 0; REP(i, n) { scanf("%d", &p[0][i].d); p[0][i].id = i; p[1][i] = p[0][i]; tot += p[0][i].d; } if(tot&1) puts("IMPOSSIBLE"); else { tot /= 2; if(!solve(p[0], e1)) puts("IMPOSSIBLE"); else { if(gao(p[1], e2)) { puts("MULTIPLE"); print(e1); print(e2); } else { puts("UNIQUE"); print(e1); } } } } return 0; }

좋은 웹페이지 즐겨찾기