zoj 3732 그래프 재 구성 (구조)
먼저 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.