POJ-1659 Frogs' Neighborhood

本文主要是介绍POJ-1659 Frogs' Neighborhood，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这里是原题地址：Frogs' Neighborhood

算法的在我的另一篇博文里讲的比较清楚了Havel–Hakimi algorithm

这里直接贴代码，是用stl优先队列实现的，内存消耗比较大

/*****************************************************************> File Name: POJ1606.cpp> Author: Uncle_Sugar> Mail: uncle_sugar@qq.com> Created Time: 2015年10月10日 星期六 22时20分44秒****************************************************************/
# include <cstdio>
# include <iostream>
# include <vector>
# include <cstring>
# include <queue>
using namespace std;const int debug = 0;
const int size = 15;
int g[size][size];typedef pair<int,int> vertex;
int main()
{int i,j,k;int T,Case = 0;scanf("%d",&T);while (T--){memset(g,0,sizeof(g));if (Case++) printf("\n");int n;scanf("%d",&n);vector<vertex> seq;for (i=0;i<n;i++){int tmp;scanf("%d",&tmp);seq.push_back(vertex(tmp,i));}priority_queue<vertex> pri_que;for (i=0;i<seq.size();i++)if (seq[i].first)pri_que.push(seq[i]);int flag = 1;while (!pri_que.empty()){int degree = pri_que.top().first;int number = pri_que.top().second;pri_que.pop();if (pri_que.size()<degree){flag = 0;break;}vector<vertex> vct;while (degree--){vertex tmp = pri_que.top();pri_que.pop();tmp.first--;g[number][tmp.second] = g[tmp.second][number] = 1;vct.push_back(tmp);}for (i=0;i<vct.size();i++)if (vct[i].first)pri_que.push(vct[i]);}if (flag){printf("YES\n");for (i=0;i<n;i++)for (j=0;j<n;j++)printf("%d%c",g[i][j],j==n-1?'\n':' ');}else printf("NO\n");}return 0;
}