- 題意

給出我們從1-n城市的點能直接（或間接）到達的城市的數量作為這個點的權值 讓我們判斷并構造一個單向圖 使得這個圖完全契合給出的數據 special judge 任意一組結果就可以題目中給出 圖中無環無回路

- 分析

剛看到根據聯通數目構造圖 哇 這怎么做 好復雜啊！這該如何構造？？ 其實想一下就可以發現 題目中說是一個無環圖 也就是說

任何一個有向無環圖中必定至少存在一個入度為0的頂點，至少存在一個出度為0的頂點，否則圖中必存在環。有向無環圖對于構造一個任務必須發生在另一個任務之前的這種依賴模型特別有效。有向無環圖的另一個應用是規劃項目，例如建造房屋時，框架的設計必須在蓋屋頂之前。

否則 如果無環圖中的每一個點都有出度的話 這與無環的性質矛盾 我們說 一個無環圖就是一個可以被拓補排序的圖 也就說 這個圖 一定可以被拓撲排序 所以我們發現 低權值的點 不會連向高權值的點 因為一個低權值的點 如果連向一個比自己權值高的點就會產生矛盾 所以當我們把低權值的點處理完后 把每一層低權值的點處理完后 相應的高一層的點就相當于單個點 就像拓撲排序 因為高一層的點來自低一層的點 所以我們從低到高處理 每處理完一層點比其只高一層的點 就相當于單個點 就像是拓撲排序的步驟 每排好一個點 就把這個點的出度全部刪除 這里同理 每選完一個點 就把這個點 直接到達的點看成 無入度點 所以就可以一個個選了 生序排序 從低到高處理 相當于反向拓撲排序的步驟 如果這個處理的這個點 找不到足夠的點 可以連 就輸出NO 證明一個有向圖是有向無環圖方法： 拓撲排序方法

code

#include<bits/stdc++.h> using namespace std; vector<int>v[1010]; struct node{int o,val; }a[1010]; bool cmp(node aa,node bb){return aa.val<bb.val; } int main() {int p,t,n;scanf("%d",&t);for( p=1;p<=t;p++){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i].val);a[i].o = i;}printf("Case #%d: ",p);sort(a+1,a+1+n,cmp);if(a[1].val!=0){puts("No");continue;}int i,c=0,j;bool f=0;for(i=1;i<=n;i++){if(a[i].val==0)continue;for(j=1;j<i&&j<=a[i].val;j++){v[a[i].o].push_back(a[j].o);c++;}if(v[a[i].o].size()!=a[i].val){f=1;break;}}if(f)puts("No");else{puts("Yes");printf("%d\n",c);for(int i=1;i<=n;i++)for(int j=0;j<v[i].size();j++)printf("%d %d\n",i,v[i][j]);}for(int i=1;i<=n;i++)v[i].clear();}return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

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

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