XJOI1689相连的城市

相连的城市

n个城市中，某些城市间有道路互相连接。给出与每个城市相邻的城市有多少个，请输出城市间的邻接矩阵。

输入格式：

第一行输入一个正整数n，表示城市的个数。
第二行输入n个用空格隔开的非负整数，其中第i个数表示与城市i相邻的城市有多少个。

输出格式：

输出满足输入数据的邻接矩阵。也就是说，你的输出应该一个关于对角线对称的N x N的01矩阵。输出的数需要用空格隔开。
如果没有满足条件的邻接矩阵，请输出“No Solution”。
如果有多种可能的邻接矩阵，你可以任意输出一个。

样例输入：

7
4 3 1 5 4 2 1

样例输出：

（不唯一）
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

数据范围：

对于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;
在处理过程中，为了避免每次操作都快速排序（N²*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");
     }
     ;
 }

巴特西