hdu 5813 Elegant Construction

???? 水題

　　題意：有n個城市，給你每個城市能到達城市的數量，要你構圖，輸出有向邊，要求無環，輸出任意的解

　　例：

Sample Input

3

3

2 1 0

2

1 1

4

3 1 1 0

Sample Output

Case #1: Yes

2

1 2

2 3

Case #2: No

Case #3: Yes

4

1 2

1 3

2 4

3 4

　　想法：不構成環，就是最終有一個邊為零，所以至少有一城市能到達的城市數為零，所以可以逐層的連向零點的邊，如果最后為都為零，表示構圖成功，否則失敗

　　代碼：

#include <iostream>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 110000
using namespace std;struct node
{int v,i;} a[1100];
bool cmp(node a,node b)
{return a.v<b.v;
}
int b[1000000+88][2];int main()
{int t;cin>>t;int dd=0;while(t--){int n;cin>>n;for(int i=1; i<=n; i++){cin>>a[i].v;a[i].i=i;}sort(a+1,a+n+1,cmp);int ans=0;bool faa=true;for(int i=1; i<=n; i++){if(a[i].v!=0){printf("Case #%d: No\n",++dd);faa=false;break;}bool fa=true;for(int q=i; q<=n; q++){if(a[q].v!=0)fa=false;}if(fa){printf("Case #%d: Yes\n",++dd);break;}for(int q=i; q<=n; q++){if(a[q].v!=0){b[ans][0]=a[q].i;b[ans++][1]=a[i].i;a[q].v--;}}}if(faa){printf("%d\n",ans);for(int i=0; i<ans; i++){printf("%d %d\n",b[i][0],b[i][1]);}}}return 0;
}

?