程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDOJ題目2454 Degree Sequence of Graph G(判斷是否是簡單圖)

HDOJ題目2454 Degree Sequence of Graph G(判斷是否是簡單圖)

編輯:關於C++

Degree Sequence of Graph G

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1811 Accepted Submission(s): 750


Problem Description 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 Knoigsberg, 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.

\

AccZ喎?/kf/ware/vc/" target="_blank" class="keylink">vcmRpbmcgdG8gR3JhcGggVGhlb3J5LCB0aGUgbnVtYmVyIG9mIGVkZ2VzIHJlbGF0ZWQgdG8gYSBub2RlIGlzIGRlZmluZWQgYXMgRGVncmVlIG51bWJlciBvZiB0aGlzIG5vZGUuPGJyPgo8YnI+CldhbmcgSGFpeWFuZyBsb29rZWQgYXQgdGhlIGdyYXBoIGFuZCB0aG91Z2h0LCBJZiBhcnJhbmdlZCwgdGhlIERlZ3JlZSBudW1iZXJzIG9mIGFsbCBub2RlcyBvZiBncmFwaCBHIGNhbiBmb3JtIHN1Y2ggYSBzZXF1ZW5jZTogNCwgNCwgMywzLDIsMiwgd2hpY2ggaXMgY2FsbGVkIHRoZSBkZWdyZWUgc2VxdWVuY2Ugb2YgdGhlIGdyYXBoLiBPZiBjb3Vyc2UsIHRoZSBkZWdyZWUgc2VxdWVuY2Ugb2YgYW55IHNpbXBsZSBncmFwaCAoYWNjb3JkaW5nIHRvCiBHcmFwaCBUaGVvcnksIGEgZ3JhcGggd2l0aG91dCBhbnkgcGFyYWxsZWwgZWRnZSBvciByaW5nIGlzIGEgc2ltcGxlIGdyYXBoKSBpcyBhIG5vbi1uZWdhdGl2ZSBpbnRlZ2VyIHNlcXVlbmNlPzxicj4KPGJyPgpXYW5nIEhhaXlhbmcgaXMgYSB0aG91Z2h0ZnVsIHBlcnNvbiBhbmQgdGVuZHMgdG8gdGhpbmsgZGVlcGx5IG92ZXIgYW55IHNjaWVudGlmaWMgcHJvYmxlbSB0aGF0IGdyYWJzIGhpcyBpbnRlcmVzdC4gU28gYXMgdXN1YWwsIGhlIGFsc28gZ2F2ZSB0aGlzIHByb2JsZW0gZnVydGhlciB0aG91Z2h0LCBBcyB3ZSBrbm93LCBhbnkgYSBzaW1wbGUgZ3JhcGggYWx3YXlzIGNvcnJlc3BvbmRzIHdpdGggYSBub24tbmVnYXRpdmUgaW50ZWdlciBzZXF1ZW5jZS4KIEJ1dCB3aGV0aGVyIGEgbm9uLW5lZ2F0aXZlIGludGVnZXIgc2VxdWVuY2UgYWx3YXlzIGNvcnJlc3BvbmRzIHdpdGggdGhlIGRlZ3JlZSBzZXF1ZW5jZSBvZiBhIHNpbXBsZSBncmFwaD8gVGhhdCBpcywgaWYgZ2l2ZW4gYSBub24tbmVnYXRpdmUgaW50ZWdlciBzZXF1ZW5jZSwgYXJlIHdlIHN1cmUgdGhhdCB3ZSBjYW4gZHJhdyBhIHNpbXBsZSBncmFwaCBhY2NvcmRpbmcgdG8gaXQuPzxicj4KPGJyPgpMZXQ="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?


Input 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.


Output For each case, the answer should be "yes"or "no" indicating this case is "draw-possible" or "non-draw-possible"


Sample Input
2
6 4 4 3 3 2 2
4 2 1 1 1

Sample Output
yes
no

Source 2008 Asia Regional Harbin
Recommend gaojie | We have carefully selected several similar problems for you: 2448 2452 2451 2453 2455 ac代碼
#include
#include
#include
int cmp(const void *a,const void *b)
{
	return *(int *)b-*(int *)a;
}
int a[10010];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,i,j,sum=0;
		scanf("%d",&n);
		for(i=0;i=n)
				break;
		}
		if(i

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved