uva 10720 Graph Construction
Graph is a collection of edges E and verticesV. Graph has a wide variety of applications in computer. There are different ways to represent graph in computer. It can be represented by adjacency matrix or by adjacency list. There are some other ways to represent graph. One of them is to write the degrees (the numbers of edges that a vertex has) of each vertex. If there aren vertices then n integers can represent that graph. In this problem we are talking about simple graph which does not have same endpoints for more than one edge, and also does not have edges with the same endpoint.
Any graph can be represented by n number of integers. But the reverse is not always true. If you are givenn integers, you have to find out whether this n numbers can represent the degrees ofn vertices of a graph.
InputEach line will start with the number n (≤ 10000). The nextn integers will represent the degrees of n vertices of the graph. A 0 input for n will indicate end of input which should not be processed.
OutputIf the n integers can represent a graph then print “Possible”. Otherwise print “Not possible”. Output for each test case should be on separate line.
Sample Input
Output for Sample Input
4 3 3336 2 4 5 5 2 15 3 2 3 2 10
PossibleNot possibleNot possible
题目大意：给出一张有n个点的图，，然后再给出每个点的度数。求这个图是否可能存在。
解题思路：注意剪枝。
#include<stdio.h>#include<string.h>#include<stdlib.h>#include<algorithm>using namespace std;int degree[10005];int cmp(int a, int b) {return a > b;}int main() {int n;while (scanf("%d", &n), n) {int sum = 0, flag = 1;memset(degree, 0, sizeof(degree));for (int i = 0; i < n; i++) {scanf("%d", °ree[i]);if (degree[i] >= n) flag = 0; //出现多余的度数sum += degree[i];}if (sum % 2) { //各节点度数不匹配printf("Not possible\n");continue;}if (sum == 0) { //总度数为零printf("Possible\n");continue;}if (!flag) {printf("Not possible\n");continue;}int flag2 = 1;for (int i = 0; i < n – 1; i++) {sort(degree + i, degree + n, cmp);if (i + degree[i] >= n) {flag = 0;flag2 = 0;}if (!flag2) break;for (int j = i + 1; j <= i + degree[i]; j++) {degree[j]–;if (degree[j] < 0) {flag = 0;flag2 = 0;}}if (!flag2) break;}if (degree[n – 1] != 0) flag = 0; //度数不匹配if (flag) printf("Possible\n");else printf("Not possible\n");}return 0;}
好好的管教你自己，不要管别人。
