解題區/解題區 - UVa

UVa 12365 - Jupiter Atacks

Problem

查詢區間 hash 值、支持修改單一元素。

Sample Input

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
20 139 5 7
E 1 12
E 2 14
E 3 2
E 4 2
E 5 4
H 2 5
E 2 14
10 1000003 6 11
E 1 3
E 2 4
E 3 5
E 4 6
E 5 7
E 6 8
H 1 6
E 3 0
E 3 9
H 1 3
H 4 6
999999935 999999937 100000 7
E 100000 6
E 1 7
H 1 100000
E 50000 8
H 1 100000
H 25000 75000
H 23987 23987
0 0 0 0

Sample Output

1
2
3
4
5
6
7
8
9
10
11
115
-
345678
349
678
-
824973478
236724326
450867806
0
-

Solution

線段樹套用

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long B, P; 
long long tree[262144 + 10], shiftP[131072 + 10];
void modify(int k, int l, int r, int x, int val) {
    if(l > r)	return;
    if(l == r) {
        tree[k] = val;	return ;
    }
    int m = (l + r)>>1;
    if(x <= m)	
        modify(k<<1, l, m, x, val);
    else		
        modify(k<<1|1, m+1, r, x, val);
    tree[k] = (tree[k<<1]*shiftP[r - m] + tree[k<<1|1])%P;
}
long long query(int k, int l, int r, int x, int y) {
    if(l > r)	return 0;
    if(x <= l && r <= y) {
        return tree[k]*shiftP[y - r];
    }
    int m = (l + r)>>1;
    long long ret = 0;
    if(x <= m)
        ret += query(k<<1, l, m, x, y);
    if(y > m)
        ret += query(k<<1|1, m+1, r, x, y);
    return ret%P;
}
int main() { 
    char cmd[1024];
    int a, b, n, q;
    while(scanf("%lld %lld %d %d", &B, &P, &n, &q) == 4 && n) {
        shiftP[0] = 1;
        for(int i = 1; i <= n; i++)
            shiftP[i] = (shiftP[i - 1] * B)%P;
        memset(tree, 0, sizeof(tree));
        while(q--) {
            scanf("%s %d %d", cmd, &a, &b);
            if(cmd[0] == 'E')
                modify(1, 1, n, a, b);
            else
                printf("%lld\n", query(1, 1, n, a, b));
        }
        puts("-");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12357 - Ball Stacking

Problem

給一個球球堆起的三角堆，抽走一顆球或者使其他球滑落到其他地方 (失去支撐)，則所有落下、拿走的球將會是得到的分數。求最多能獲得多少分數。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
4
3
-5 3
-8 2 -8
3 9 -2 7
2
-2
1 -10
3
1
-5 3
6 -4 1
0

Sample Output

1
2
3
7
0
6

Solution

面對三角堆，我們由左往右、由上而下考慮是否要將球移開，而這麼做很容易得到一個 O(n^3) 的做法，利用輔助數據壓縮在 O(n^2) 完成 (因為中間有一段迴圈是找後綴最大值)。

轉移的時候也很簡單，考慮兩種情況

  1. 只考慮移除自己的時候落下的所有球
  2. 考慮與前一列別處拿走所產生的交集情況

在第二種可以發現，如果考慮左側高於自己的球球被移除的情況可以忽略不計。

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
32
33
34
35
36
37
#include <stdio.h> 
#include <string.h>
#include <algorithm> 
using namespace std;
int g[1024][1024] = {}, w[1024][1024] = {};
int dp[1024][1024] = {}, sdp[1024][1024] = {};
int main() {
    int n;
    while(scanf("%d", &n) == 1 && n) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                scanf("%d", &g[i][j]);
                g[i][j] += g[i-1][j];
            }
        }
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= i; j++)
                w[i][j] = g[i][j] + w[i-1][j-1];
        int ret = 0;
        memset(dp, 0, sizeof(dp));
        for(int j = 1; j <= n; j++) {
            for(int i = j; i <= n; i++) {
                dp[i][j] = w[i][j];
//				for(int k = i-1; k <= n; k++)
//					dp[i][j] = max(dp[i][j], dp[k][j-1] + g[i][j]);
                dp[i][j] = max(dp[i][j], sdp[i-1][j-1] + g[i][j]);
                ret = max(ret, dp[i][j]);
            }
            sdp[n][j] = dp[n][j];
            for(int i = n - 1; i >= j; i--)
                sdp[i][j] = max(sdp[i+1][j], dp[i][j]);
        }
        printf("%d\n", ret);
    } 
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12338 - Anti-Rhyme Pairs

Problem

給一堆單詞，問任意兩個單詞的最常共同前綴長為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
5
daffodilpacm
daffodiliupc
distancevector
distancefinder
distinctsubsequence
4
1 2
1 5
3 4
4 5
2
acm
icpc
2
1 2
2 2

Output for Sample Input

1
2
3
4
5
6
7
8
Case 1:
8
1
8
4
Case 2:
0
4

Solution

對每一個單詞插入到 Trie 中，詢問任兩個字串的最長共同前綴時，相當於詢問兩個節點之間的最小共同祖先距離根多遠。

解決 LCA 問題，這裡採用離線 tarjan 做法。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
struct Trie {
    int n, label, dist;
    int link[26];
} Node[1048576];
int TrieSize;
int insertTrie(const char* str) {
    static int i, idx;
    for(i = idx = 0; str[i]; i++) {
        if(Node[idx].link[str[i]-'a'] == 0) {
            TrieSize++;
            memset(&Node[TrieSize], 0, sizeof(Node[0]));
            Node[TrieSize].label = TrieSize;
            Node[TrieSize].dist = i + 1;
            Node[idx].link[str[i]-'a'] = TrieSize;
        }
        idx = Node[idx].link[str[i]-'a'];
    }
    Node[idx].n ++;
    return Node[idx].label;
}
vector< pair<int, int> > Q[1048576];// query pair, v - input index.
int visited[1048576], F[1048576];
int LCA[1048576];//input query answer buffer.
int findF(int x) {
    return F[x] == x ? x : (F[x]=findF(F[x]));
}
void tarjan(int u) {// rooted-tree.
    F[u] = u;
    for(int i = 0; i < 26; i++) {//son node.
        int v = Node[u].link[i];
    	if(v == 0)	continue;
        tarjan(v);
        F[findF(v)] = u;
    }
    visited[u] = 1;
    for(int i = 0; i < Q[u].size(); i++) {
        if(visited[Q[u][i].second]) {
            LCA[Q[u][i].first] = findF(Q[u][i].second);
        }
    }
}
int main() {
    int testcase, cases = 0, x, y, n;
    int mp[131072];
    char s[32767];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        TrieSize = 0;
        memset(&Node[0], 0, sizeof(Node[0]));
        for(int i = 1; i <= n; i++) {
        	scanf("%s", s);
        	int x = insertTrie(s);
        	mp[i] = x;
        }
        scanf("%d", &n);
        
        for(int i = 0; i <= TrieSize; i++)
            visited[i] = 0, Q[i].clear();
        for(int i = 0; i < n; i++) {
        	scanf("%d %d", &x, &y);
        	Q[mp[x]].push_back(make_pair(i, mp[y]));
        	Q[mp[y]].push_back(make_pair(i, mp[x]));
        }
        tarjan(0);
        printf("Case %d:\n", ++cases);
        for(int i = 0; i < n; i++) {
            printf("%d\n", Node[LCA[i]].dist);
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12316 - Sewing Buttons with Grandma

Problem

有 N 種不同顏色的鈕扣，每一種燈泡分別有 $n_{i}$ 個，請問拿 M 個鈕扣獲得的組合類型有多少種。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
1 3
3
1
1
3 2
4
2
3 2
1
1
0 0

Sample Output

1
2
3
3
7
0

Solution

組合問題，相當於計算以下式子的整數解。

$$x_{1} + x_{2} + x_{3} + .. + x_{n} = M \\ 0 \le x_{i} \le n_{i}$$

事實上，利用 dp[i][j] 表示考慮前 i 種湊出 j 個組合數，得到 dp[i][j + k] += dp[i - 1][j] * C[j + 1 + k][k] 加入新種類的鈕扣。

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
32
33
34
35
36
37
38
39
40
41
import java.util.Scanner;
import java.math.BigInteger;
public class Main {
    public static void main(String[] args) {
        BigInteger[][] C = new BigInteger[128][128];
        for (int i = 0; i < 128; i++)
            for (int j = 0; j < 128; j++)
                C[i][j] = BigInteger.ZERO;
        for (int i = 1; i < 128; i++) {
            C[i][0] = BigInteger.ONE;
            for (int j = 1; j <= i; j++)
                C[i][j] = C[i - 1][j].add(C[i - 1][j - 1]);
        }
        Scanner cin = new Scanner(System.in);
        int n, m;
        int[] A = new int[128];
        while (cin.hasNext()) {
            n = cin.nextInt();
            m = cin.nextInt();
            if (n + m == 0)
                break;
            for (int i = 1; i <= m; i++)
                A[i] = cin.nextInt();
            BigInteger[][] dp = new BigInteger[128][128];
            for (int i = 0; i < 128; i++)
                for (int j = 0; j < 128; j++)
                    dp[i][j] = BigInteger.ZERO;
            dp[0][0] = BigInteger.ONE;
            for (int i = 1; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    for (int k = 0; k <= A[i] && j + k <= n; k++)
                        dp[i][j + k] = dp[i][j + k].add(dp[i - 1][j]
                                .multiply(C[j + k + 1][k]));
                }
            }
            System.out.println(dp[m][n]);
        }
    }
}

附上一個 C++ 的版本，由於沒有使用 BigInteger 而 Wrong Answer.

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
#include <stdio.h> 
long long C[128][128], A[128];
int main() {
    for(int i = 1; i < 128; i++) {
        C[i][0] = 1;
        for(int j = 1; j <= i; j++)
            C[i][j] = C[i-1][j] + C[i-1][j-1];
    }
    int n, m;
    while(scanf("%d %d", &n, &m) == 2 && n+m) {
        for(int i = 1; i <= m; i++)
            scanf("%lld", &A[i]);
        long long dp[128][128] = {};
        
        dp[0][0] = 1;
        for(int i = 1; i <= m; i++) {
            for(int j = 0; j <= n; j++) {
                for(int k = 0; k <= A[i] && j + k <= n; k++)
                    dp[i][j + k] += dp[i - 1][j] * C[j + 1 + k][k];
            }
        }
        printf("%lld\n", dp[m][n]);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12302 - Nine-Point Circle

Problem

給三角形三點座標，求通過三高三點和三邊中點的圓為何？

Sample Input

1
2
0 0 10 0 3 4
-1 -1 -1 -1 -1 -1

Output for the Sample Input

1
4.000000 2.312500 2.519456

Solution

直接對三邊中點做外心即可。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator/(const double a) const {
        return Pt(x/a, y/a);
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dist2(Pt a, Pt b) {
    return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
}
double length(Pt a) {
    return hypot(a.x, a.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
}
double angle(Pt a, Pt b) {
    return acos(dot(a, b) / length(a) / length(b));
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
Pt getIntersection(Pt p, Pt l1, Pt q, Pt l2) {
    double a1, a2, b1, b2, c1, c2;
    double dx, dy, d;
    a1 = l1.y, b1 = -l1.x, c1 = a1 * p.x + b1 * p.y;
    a2 = l2.y, b2 = -l2.x, c2 = a2 * q.x + b2 * q.y;
    d = a1 * b2 - a2 * b1;
    dx = b2 * c1 - b1 * c2;
    dy = a1 * c2 - a2 * c1;
    return Pt(dx / d, dy / d);
}
Pt circle(Pt a, Pt b, Pt c) {
    Pt mab = (a + b)/2;
    Pt mbc = (b + c)/2;
    Pt lab = b - a, lbc = c - b;
    swap(lab.x, lab.y);
    swap(lbc.x, lbc.y);
    lab.x = -lab.x;
    lbc.x = -lbc.x;
    return getIntersection(mab, lab, mbc, lbc);
}
int main() {
    Pt a, b, c, o;	
    while(true) {
        scanf("%lf %lf", &a.x, &a.y);
        scanf("%lf %lf", &b.x, &b.y);
        scanf("%lf %lf", &c.x, &c.y);
        if(a.x < 0)	break;
        o = circle((a + b)/2, (b + c)/2, (c + a)/2);
        printf("%lf %lf %lf\n", o.x, o.y, dist(o, (a + b)/2));
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12300 - Smallest Regular Polygon

Problem

二維平面中，給兩個點座標，以及一個 N，找到一個正 N 邊形，邊上通過這兩個點座標。求該正 N 邊形的最小面積為何？

Sample Input

1
2
3
4
0 0 1 1 4
1 2 3 4 5
2 3 4 5 6
0 0 0 0 0

Output for the Sample Input

1
2
3
1.000000
5.257311
5.196152

Solution

最小面積的正 N 邊形，保證通過兩點一定在正 N 邊行的兩個頂點，而不會出現在邊上。

分開討論奇偶數，奇數直接是對角線，偶數則偏離一點。找到兩點與圓心(正 N 邊形外接圓)拉出的三角形，根據張開的角度計算外接圓的半徑即可。

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
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#include <math.h>
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator/(const double a) const {
        return Pt(x/a, y/a);
    }
    int read() {
    	return scanf("%lf %lf", &x, &y);
    }
};
int main() {
    Pt A, B;
    const double pi = acos(-1); 
    int n;
    while(true) {
        A.read(), B.read(), scanf("%d", &n);
        if(n == 0)	break;
        double r, dist = hypot(A.x - B.x, A.y - B.y);
        if(n%2 == 0) {
            r = dist /2;
        } else {
            int m = (n - 1)/2;
            r = dist /2 / sin((double)m/2.0/n * 2 * pi);
        }
        printf("%lf\n", r * r * sin(2 * pi/n) * n/2);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12283 - Halloween Costumes

Problem

依序參加派對，每一個派對要求的服裝可能有所不同，可以衣服一件套一件去參加下一場派對，一旦脫下來服裝將不會穿第二次，請問至少要準備幾件才能參與所有派對。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
4 
1 1 
1 
2 2 
1 1 
3 2 
1 2 1 
7 3 
1 2 1 1 3 2 1

Sample Output

1
2
3
4
Case 1: 1
Case 2: 1
Case 3: 2
Case 4: 4

Solution

dp[l][r] 表示參與區間 [l, r] 從 l 開始的最少服裝數。

假設一開始已經穿著 l-th 的服裝，則將可以在參加完後脫掉，或者是到同一個另外一個場所之後考慮是否要脫掉。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
int dp[105][105], a[105];
int dfs(int l, int r) {
    if(l > r)	return 0;
    int &ret = dp[l][r];
    if(ret != -1)	return ret;
    ret = min(dfs(l+1, r), dfs(l, r-1))+1;
    for(int i = l+1; i <= r; i++) {
        if(a[l] == a[i])
            ret = min(ret, dfs(l+1, i) + dfs(i+1, r));
    }
    return ret;
}
int main() {
    int cases = 0, testcase, n, m;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        memset(dp, -1, sizeof(dp));
        printf("Case %d: %d\n", ++cases, dfs(0, n-1));
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12260 - Free Goodies

Problem

有n个糖果，每个糖果有p，j两个值，现在有两个人Petra和Jan，Prtra的取糖果方式是优先去p值大的j值小的；Jan取糖果的方式是尽量让自己开心值（取出糖果的j值和）大的情况下让Petra的开心值（取出糖果的p值和）也大，给出先选糖果的人，问说最后两人的开心值分别为多少。

這裡可以明白有兩種策略

  • Petra 只求讓自己最高 - 貪心
  • Jan 自己最高的情況下，Petra 盡可能地高

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
3
4
Petra
100 80
70 80
50 80
30 50
4
Petra
10 1
1 10
6 6
4 4
7
Jan
4 1
3 1
2 1
1 1
1 2
1 3
1 4

Sample

1
2
3
170 130
14 16
9 10

Solution

Petra 使用貪心，將糖果數值按照 P 降排序，來作為 dp 時候 Petra 轉移用的順序，只要確保 Petra 會根據這個順序從大挑到小。

並且確保前 i 個糖果時，Jan 不會拿超過 i/2 個糖果 (否則表示交替順序不符合規則)，Jan 可以選擇先讓 Petra 分配到大的 P，而自己先去取大的 J。

dp[i][j] 表示前 i 個糖果，Jan 分配到 j 個的最佳策略 (J, P)。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h> 
#include <string.h>
#include <algorithm>
#include <functional>
using namespace std;
const char name[2][10] = {"Petra", "Jan"};
pair<int, int> D[1024];
pair<int, int> dp[1024][512];
bool cmp(pair<int, int> p, pair<int, int> q) {
    if(p.first != q.first)
        return p.first > q.first;
    return p.second < q.second;
}
int main() {	
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
    int testcase, n;
    char s[1024];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %s", &n, s);
        
        for(int i = 1; i <= n; i++) {
            int p, j;
            scanf("%d %d", &p, &j);
            D[i] = make_pair(p, j);
        }
        sort(D+1, D+1+n, cmp);
        
        int base = 0;
        if(!strcmp(name[0], s)) {
            base = D[1].first;
            for(int i = 1; i < n; i++)
                D[i] = D[i+1];
            n--;
        }
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= (i+1)/2; j++) {
                dp[i][j] = make_pair(dp[i-1][j].first, dp[i-1][j].second + D[i].first);
                if(j)
                    dp[i][j] = max(dp[i][j], 
                        make_pair(dp[i-1][j-1].first + D[i].second, dp[i-1][j-1].second));
            }
        }
        printf("%d %d\n", dp[n][(n+1)/2].second + base, dp[n][(n+1)/2].first);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11893 - Fabulous DAGy

Problem

原本是一張 DAG，增加一條有向邊會使得存有一個環，而這個環將會通過所有的點一次。

現在給予加完後的結果，是否存在一條有向邊，使得原本的 DAG 變成符合上述條件的圖。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
2
3 3
0 1
1 2
2 0
4 5
0 1
1 2
2 0
0 3
3 2

Sample Output

1
2
Yeah, I'm superman
Your DAGy was initially defected!

Solution

由於只能通過所有點一次的環，對於 DAG 而言，替除掉應該加入的邊會發現到拓樸排序只能是唯一的長鏈狀。

因此窮舉拔掉所有可能的邊，並且檢查是否能夠符合長鏈狀的拓樸順序。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int indeg[512], outdeg[512], mg[512][512];
vector<int> g[512];
int check(int st, int banu, int banv, int n) {
    queue<int> Q;
    int in[512], out[512], visited = 0, u, v;
    for(int i = 0; i < n; i++)
        in[i] = indeg[i], out[i] = outdeg[i];
    Q.push(st), in[banv]--, out[banu]--;
    while(!Q.empty()) {
        u = Q.front(), Q.pop();
        visited++;
        for(int i = 0; i < g[u].size(); i++) {
            v = g[u][i];
            if(--in[v] == 0)
                Q.push(v);
        }
        if(Q.size() > 1)	return 0;
    }
    return visited == n && mg[u][st];
}
int main() {
    int testcase, n, m, u, v;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        memset(mg, 0, sizeof(mg));
        memset(indeg, 0, sizeof(indeg));
        memset(outdeg, 0, sizeof(outdeg));
        for(int i = 0; i < n; i++)
            g[i].clear();
        for(int i = 0; i < m; i++) {
            scanf("%d %d", &u, &v);
            mg[u][v] = 1;
            g[u].push_back(v);
            indeg[v]++, outdeg[u]++;
        }
        int ret = 0;
        for(int i = 0; i < n && !ret; i++) {
            for(int j = 0; j < g[i].size() && !ret; j++) {
                u = i, v = g[i][j];
                if(indeg[v] == 1 && outdeg[u] == 1) {
                    ret |= check(v, u, v, n);
                }
            }
        }
//		puts(ret ? "YES" : "NO");
        puts(ret ? "Yeah, I'm superman" : "Your DAGy was initially defected!");
    }
    return 0;
}
/*
5 6
0 1
1 2
2 3
3 4
4 0
1 3
*/
Read More +
解題區/解題區 - UVa

UVa 11874 - Travel Company

Problem

給一個 N 個城市的地圖，每一條路徑上會有成本和獲益，希望找到一條送貨的環道，是否存在一個環道使得獲益是成本的 P 倍。

Sample Input

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
3
5 8 3
0 1 17 8
1 0 10 5
1 2 11 5
1 4 5 3
2 3 13 7
3 1 9 4
4 3 11 1
3 0 11 6
5 8 3
0 1 17 8
1 0 10 5
1 2 11 5
1 4 5 3
2 3 13 7
3 1 9 4
4 3 11 2
3 0 11 6
5 8 2
0 1 17 8
1 0 10 5
1 2 11 5
1 4 5 3
2 3 13 7
3 1 9 4
4 3 11 5
3 0 11 6

Sample Output

1
2
3
Case 1: YES
Case 2: NO
Case 3: YES

Solution

最小比例環的應用，事實上可以把題目化簡為負環檢查，將每一條邊的權重定義為 expense * p - income，只要負環存在則存有一條環道的 獲益/成本 > P

點數很少，直接用 floyd 在 O(n^3) 找解。

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 <string.h>
#include <algorithm> 
using namespace std;
int g[128][128];
int main() {
    int testcase, cases = 0;
    int n, m, p, x, y, income, expense;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d %d", &n, &m, &p);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                g[i][j] = 0xf3f3f3f;
        while(m--) {
            scanf("%d %d %d %d", &x, &y, &income, &expense);
            g[x][y] = min(g[x][y], expense * p - income);
        }
        for(int k = 0; k < n; k++) {
            for(int i = 0; i < n; i++)
                for(int j = 0; j < n; j++)
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
        }
        int ret = 0;
        for(int i = 0; i < n; i++)
            ret |= g[i][i] < 0;
        printf("Case %d: %s\n", ++cases, ret ? "YES" : "NO");
    }
    return 0;
}
Read More +