Frogs' Neighborhood
| Time Limit: 5000MS | Memory Limit: 10000K | |||
| Total Submissions: 10660 | Accepted: 4433 | Special Judge | ||
Description
未名湖附近共有N个大小湖泊L1, L2, ..., Ln(其中包括未名湖)，每个湖泊Li里住着一只青蛙Fi(1 ≤ i ≤ N)。如果湖泊Li和Lj之间有水路相连，则青蛙Fi和Fj互称为邻居。现在已知每只青蛙的邻居数目x1, x2, ..., xn，请你给出每两个湖泊之间的相连关系。
Input
第一行是测试数据的组数T(0 ≤ T ≤ 20)。每组数据包括两行，第一行是整数N(2 < N < 10)，第二行是N个整数，x1, x2,..., xn(0 ≤ xi ≤ N)。
Output
对输入的每组测试数据，如果不存在可能的相连关系，输出"NO"。否则输出"YES"，并用N×N的矩阵表示湖泊间的相邻关系，即如果湖泊i与湖泊j之间有水路相连，则第i行的第j个数字为1，否则为0。每两个数字之间输出一个空格。如果存在多种可能，只需给出一种符合条件的情形。相邻两组测试数据之间输出一个空行。
Sample Input
3 7 4 3 1 5 4 2 1 6 4 3 1 4 2 0 6 2 3 1 1 2 1
Sample Output
YES 0 1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 NO YES 0 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0
Source
代码：
1 #include"bits/stdc++.h" 2 3 #define db double 4 #define ll long long 5 #define vl vector<ll> 6 #define ci(x) scanf("%d",&x) 7 #define cd(x) scanf("%lf",&x) 8 #define cl(x) scanf("%lld",&x) 9 #define pi(x) printf("%d ",x) 10 #define pd(x) printf("%f ",x) 11 #define pl(x) printf("%lld ",x) 12 #define rep(i, n) for(int i=0;i<n;i++) 13 using namespace std; 14 const int N = 1e6 + 5; 15 const int mod = 1e9 + 7; 16 const int MOD = 998244353; 17 const db PI = acos(-1.0); 18 const db eps = 1e-10; 19 const ll INF = 0x3fffffffffffffff; 20 struct P{int id,du;}; 21 P a[N]; 22 bool cmp(P a,P b){return a.du>b.du;} 23 int t,n; 24 bool s[20][20]; 25 bool cal() 26 { 27 memset(s,0, sizeof(s)); 28 for(int i=0;i<n;i++){ 29 sort(a+i,a+n,cmp); 30 if(a[i].du>n-i-1) return 0*puts("NO"); 31 for(int j=i+1;j<=i+a[i].du;j++){ 32 if(!a[j].du) return 0*puts("NO"); 33 a[j].du--; 34 int u=a[i].id,v=a[j].id; 35 s[u][v]=1,s[v][u]=1; 36 } 37 } 38 puts("YES"); 39 for(int i=0;i<n;i++) 40 for(int j=0;j<n;j++) printf("%d%c",s[i][j],j==n-1?' ':' '); 41 42 return 1; 43 } 44 int main(){ 45 ci(t); 46 for(int i=1;i<=t;i++){ 47 ci(n); 48 for(int i=0;i<n;i++) ci(a[i].du),a[i].id=i; 49 cal(); 50 if(i!=t) puts(""); 51 } 52 return 0; 53 }