解題區/解題區 - UVa

UVa 12786 - Friendship Networks

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

類似 UVa 10720 - Graph Construction，給一個無向圖的每一個節點 degree，請問是否能構成圖。

Sample Input

1
2
3
4 3 2 2 3
4 1 3 2 3
8 2 5 4 5 4 3 5 2

Sample Output

1
2
3
1
0
1

Solution

使用公式加二分。

Erdős–Gallai theorem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <algorithm>
#include <functional>
using namespace std;
int n, i, k;
long long sum[1005], d[1005];
int main() {
    while(scanf("%d", &n) == 1 && n) {
        sum[0] = 0;
        for(i = 0; i < n; i++)
            scanf("%lld", &d[i]);
        sort(d, d+n, greater<int>());
        for(i = 0; i < n; i++)
            sum[i+1] = sum[i] + d[i];
        long long left = 0, right;
        int ret = 1;
        if(sum[n]&1)    ret = 0;
        for(k = 0; k < n; k++) {
            left += d[k];
            right = (long long)k * (k+1);
            int l =  lower_bound(d , d + n, k+1, greater<int>()) - d;
            if(l < k+1)
                right += sum[n] - sum[k+1];
            else
                right += sum[n] - sum[l] + (long long)(k+1)*(l - k - 1);
            if(left > right)	ret = 0;
        }
        printf("%d\n", ret);
    }
    return 0;
}