Degree Sequence of Graph G
時間限制: 1 Sec 內(nèi)存限制: 128 MB
提交: 362 解決: 92
[提交] [狀態(tài)] [命題人:admin]
題目描述
Wang Haiyang is a strong and optimistic Chinese youngster. Although born and brought up in the northern inland city Harbin, he has deep love and yearns for the boundless oceans. After graduation, he came to a coastal city and got a job in a marine transportation company. There, he held a position as a navigator in a freighter and began his new life.

The cargo vessel, Wang Haiyang worked on, sails among 6 ports between which exist 9 routes. At the first sight of his navigation chart, the 6 ports and 9 routes on it reminded him of Graph Theory that he studied in class at university. In the way that Leonhard Euler solved The Seven Bridges of K?nigsberg, Wang Haiyang regarded the navigation chart as a graph of Graph Theory. He considered the 6 ports as 6 nodes and 9 routes as 9 edges of the graph. The graph is illustrated as below.

According to Graph Theory, the number of edges related to a node is defined as Degree number of this node.

Wang Haiyang looked at the graph and thought, “If arranged, the Degree numbers of all nodes of graph G can form such a sequence: 4, 4, 3,3,2,2, which is called the degree sequence of the graph. Of course, the degree sequence of any simple graph (according to Graph Theory, a graph without any parallel edge or ring is a simple graph) is a non-negative integer sequence”

Wang Haiyang is a thoughtful person and tends to think deeply over any scientific problem that grabs his interest. So as usual, he also gave this problem further thought, “as we know, any a simple graph always corresponds with a non-negative integer sequence. But whether a non-negative integer sequence always corresponds with the degree sequence of a simple graph? That is, if given a non-negative integer sequence, are we sure that we can draw a simple graph according to it.”

Let’s put forward such a definition: provided that a non-negative integer sequence is the degree sequence of a graph without any parallel edge or ring, that is, a simple graph, the sequence is draw-possible, otherwise, non-draw-possible. Now the problem faced with Wang Haiyang is how to test whether a non-negative integer sequence is draw-possible or not. Since Wang Haiyang hasn’t studied Algorithm Design course, it is difficult for him to solve such a problem. Can you help him?

輸入
The first line of input contains an integer T, indicates the number of test cases. In each case, there are n+1 numbers; first is an integer n (n<1000), which indicates there are n integers in the sequence; then follow n integers, which indicate the numbers of the degree sequence.

輸出
For each case, the answer should be “yes” or “no”, indicating this case is “draw-possible” or “non-draw-possible”.

樣例輸入
復(fù)制樣例數(shù)據(jù)
2
6 4 4 3 3 2 2
4 2 1 1 1
樣例輸出
yes
no

題目大意：
先輸入一個數(shù)字$T$，代表有$T$組測試數(shù)據(jù)，對每組測試數(shù)據(jù)，輸入每個點的入度和出度之和，問其是否能構(gòu)成一個簡單圖（無環(huán)也無平行邊）。

解題思路：
由于要構(gòu)成一個簡單圖，所以我們可以直接模擬建圖的過程即可，對于每個點，將其與任意$arr[i]$個點相連，$arr[i]$為這個點的度，并相應(yīng)減去對應(yīng)點得度，最后觀察是否會使得所有點的度均為0即可。

代碼：

#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <cstdlib> #include <cstring> #include <map> #include <stack> #include <queue> #include <vector> #include <bitset> #include <set> #include <utility> #include <sstream> #include <iomanip> using namespace std; typedef long long ll; typedef unsigned long long ull; #define inf 0x3f3f3f3f #define rep(i,l,r) for(int i=l;i<=r;i++) #define lep(i,l,r) for(int i=l;i>=r;i--) #define ms(arr) memset(arr,0,sizeof(arr)) //priority_queue<int,vector<int> ,greater<int> >q; const int maxn = (int)1e5 + 5; const ll mod = 1e9+7; int arr[1200]; int main() {#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);//ios::sync_with_stdio(0),cin.tie(0);int T;scanf("%d",&T);while(T--) {int n;scanf("%d",&n);bool ju=false;rep(i,1,n) {scanf("%d",&arr[i]);}bool flag = true;sort(arr+1,arr+1+n,greater<int> ());rep(i,1,n){rep(j,2,arr[1]+1){if(arr[j]>0)arr[j]--;else{flag = false;break;}}arr[1] = 0;sort(arr+1,arr+1+n,greater<int> ());if(!flag)break;}if(arr[1]>0)flag = false;if(flag)printf("yes\n");else printf("no\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Degree Sequence of Graph G【模拟】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。