相连的城市
n个城市中，某些城市间有道路互相连接。给出与每个城市相邻的城市有多少个，请输出城市间的邻接矩阵。
输入格式：
第一行输入一个正整数n，表示城市的个数。
第二行输入n个用空格隔开的非负整数，其中第i个数表示与城市i相邻的城市有多少个。
输出格式：
输出满足输入数据的邻接矩阵。也就是说，你的输出应该一个关于对角线对称的N x N的01矩阵。输出的数需要用空格隔开。
如果没有满足条件的邻接矩阵，请输出“No Solution”。
如果有多种可能的邻接矩阵，你可以任意输出一个。
样例输入：
74 3 1 5 4 2 1
样例输出：
（不唯一）0 1 0 1 1 0 11 0 0 1 1 0 00 0 0 1 0 0 01 1 1 0 1 1 01 1 0 1 0 1 00 0 0 1 1 0 01 0 0 0 0 0 0
数据范围：
对于30%的数据，n<=3；
对于50%的数据，n<=30；
对于70%的数据，n<=300；
对于100%的数据，n<=3000；
读入时第2行读a[1]..a[n]
for k:=1 to n do
begin
找度最大 也就是相邻城市最多的点i,度为max;
if max=0 then break;
{选出第2大，第3大...第a[i]+1大的度不为零的点与他连接 这a[i]个点设为x1,x2,x3...xa[i] 让这a[i]个点都-1即dec(a[x1]);dec(a[x2])……}
a[i]:=0; {把a[i]变为0;}
end;
在处理过程中，为了避免每次操作都快速排序（N2*logN太大）我采用归并排序，开一个A数组，A中与city都是按照con（connection连接）从大到小排列的，然后把处理过的A与city归并。
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; ; bool map[N][N]; struct node{ int num,con; }city[N],A[N]; inline bool cmp(node a,node b){return a.con>b.con;} int main() { int n; scanf("%d",&n); ;i<=n;i++) { city[i].num=i; scanf("%d",&city[i].con); } sort(city+,city+n+,cmp); int w,pa,pc,pn; ;i<=n;i++) { ].con==) break; w=city[].con; ;j<=+w;j++) { map[city[].num][city[j].num]=map[city[j].num][city[].num]=; A[j-]=city[j]; A[j-].con--; } A[w+]=city[]; A[w+].con=; pa=;pc=w+;pn=; &&pc<=n) { if(A[pa].con>city[pc].con) city[pn++]=A[pa++]; else city[pn++]=city[pc++]; } ) city[pn++]=A[pa++]; while(pc<=n) city[pn++]=city[pc++]; } ;i<=n;i++) { ;j<=n;j++) printf("%d ",map[i][j]); printf("\n"); } ; }
