???? 水題

　　題意：有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; } View Code

?

轉載于:https://www.cnblogs.com/aishuijdemiaomiao/p/5754966.html

總結

以上是生活随笔為你收集整理的hdu 5813 Elegant Construction的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。