POJ-1659 Frogs'Neighborhood Havel-Hakimi 정리|욕심 을 도 출 할 수 있 습 니 다.

제목 링크:http://poj.org/problem?id=1659
그림 이 없 는 도 순 서 를 지정 하여 그림 의 인접 행렬 을 구 합 니 다.만약 이 서열 이 그림 을 구성 할 수 있다 면,이 서열 을 그림 이 라 고 부른다.여기 가 바로 구도 서열 이 그림 화 될 수 있 는 지 여 부 를 구 하 는 것 이다.사실 알고리즘 은 곰 곰 이 생각해 보면 생각해 낼 수 있 는데 그 때 는 정렬 이 라 고 생각 하고 욕심 을 내 서 선택 했다.그 과정 은 바로 Havel-Hakimi 의 정리 이다.
               1.도 시퀀스 가 비 오름차 순 으로 정렬 됨
               2.도 서열 의 첫 번 째 수 에서 그 후의 점 구성 변 으로 그 도수 가 다 떨 어 질 때 까지.만약 다 쓰 지 않 았 다 면,그림 화 할 수 없 었 을 것 이다.
               3.도수 가 다 떨 어 지면 구도 가 완성 되 고 그렇지 않 으 면 첫 번 째 단 계 를 진행한다.

 1 //STATUS:C++_AC_0MS_164KB

 2 #include<stdio.h>

 3 #include<stdlib.h>

 4 #include<string.h>

 5 #include<math.h>

 6 #include<iostream>

 7 #include<string>

 8 #include<algorithm>

 9 #include<vector>

10 #include<queue>

11 #include<stack>

12 using namespace std;

13 #define LL __int64

14 #define pdi pair<int,int>

15 #define Max(a,b) ((a)>(b)?(a):(b))

16 #define Min(a,b) ((a)<(b)?(a):(b))

17 #define mem(a,b) memset(a,b,sizeof(a))

18 #define lson l,mid,rt<<1

19 #define rson mid+1,r,rt<<1|1

20 const int N=30,M=1000000,INF=0x3f3f3f3f,MOD=1999997;

21 const LL LLNF=0x3f3f3f3f3f3f3f3fLL;

22 const double DNF=100000000000;

23 

24 struct Node{

25     int a,id;

26 }num[N];

27 int w[N][N];

28 int T,n;

29 

30 int cmp(const Node& a,const Node& b)

31 {

32     return a.a>b.a;

33 }

34 

35 int main()

36 {

37  //   freopen("in.txt","r",stdin);

38     int i,j,ok;

39     scanf("%d",&T);

40     while(T--)

41     {

42         ok=1;

43         mem(w,0);

44         scanf("%d",&n);

45         for(i=0;i<n;i++){

46             scanf("%d",&num[i].a);

47             num[i].id=i;

48         }

49 

50         for(i=0;i<n;i++){

51             sort(num,num+n,cmp);

52             for(j=1;j<n && num[0].a;j++){

53                 if(num[j].a){

54                     num[0].a--;num[j].a--;

55                     w[num[0].id][num[j].id]=w[num[j].id][num[0].id]=1;

56                 }

57              }

58              if(num[0].a){ok=0;break;}

59         }

60 

61         if(!ok)printf("NO
");

62         else {

63             printf("YES
");

64             for(i=0;i<n;i++){

65                 printf("%d",w[i][0]);

66                 for(j=1;j<n;j++)

67                     printf(" %d",w[i][j]);

68                 putchar('
');

69             }

70         }

71         if(T)putchar('
');

72     }

73     return 0;

74 }