解題區/解題區 - UVa

UVa 12745 - Wishmaster

Problem

有 n 個地點，每個地點要不用高架橋、要不使用地下化道路兩種方式，每個民眾有兩個願望，分別希望哪裡以什麼方式建造，只要滿足每一個民眾的其中一種願望即可。

Sample Input

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

Sample Output

1
2
Case 1: No
Case 2: Yes

Solution

一道樸素的 2-SAT 問題。

建圖，利用 SCC 將點縮起來，形成 DAG 圖。

如果 val 與 !val 被縮在同一個點，即為矛盾。
當關係為 (a or b) and (c or !d) and …

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
86
87
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
#define MAXN 262144
vector<int> g[MAXN];
int vfind[MAXN], findIdx;
int stk[MAXN], stkIdx;
int in_stk[MAXN], visited[MAXN];
int contract[MAXN];
int scc_cnt;
int scc(int nd) {
    in_stk[nd] = visited[nd] = 1;
    stk[++stkIdx] = nd;
    vfind[nd] = ++findIdx;
    int mn = vfind[nd];
    for(int i = 0; i < g[nd].size(); i++) {
        if(!visited[g[nd][i]])
            mn = min(mn, scc(g[nd][i]));
        if(in_stk[g[nd][i]])
            mn = min(mn, vfind[g[nd][i]]);
    }
    if(mn == vfind[nd]) {
        do {
            in_stk[stk[stkIdx]] = 0;
            contract[stk[stkIdx]] = nd;
        } while(stk[stkIdx--] != nd);
        scc_cnt++;
    }
    return mn;
}
int main() {
    int testcase, n, m, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        n = (n + 1)* 2;
        for(int i = 0; i < n; i++)
            g[i].clear();
        // 2*node: false, 2*node+1: true
        while(m--) {
        	int a, b, x, y;
        	scanf("%d %d", &a, &b);
        	x = abs(a), y = abs(b);
        	x <<= 1, y <<= 1;
        	if (a < 0)	x ^= 1;
        	if (b < 0)	y ^= 1;
        	g[x^1].push_back(y);
        	g[y^1].push_back(x);
        }
        //SCC
        memset(visited, 0, sizeof(visited));
        memset(in_stk, 0, sizeof(in_stk));
        scc_cnt = 1;
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                stkIdx = 0;
                findIdx = 0;
                scc(i);
            }
        }
        //2-SAT check
        int hasSol = 1;
        for(int i = 0; i < n && hasSol; i+=2)
            if(contract[i] == contract[i^1])
                hasSol = 0;
            
        printf("Case %d: %s\n", ++cases, hasSol ? "Yes" : "No");
    }
    return 0;
}
/*
2
3 5
-1 2
1 3
3 -2
1 -3
-2 -3
4 4
-1 2
1 3
-2 4
-3 -4
*/
Read More +
解題區/解題區 - UVa

UVa 12749 - John's Tree

Problem

目標生成一個有根樹，每個節點的 degree 最多為 V，並且樹深度恰好為 D。

請問最多有幾個節點。

Sample Input

1
2
3
4
3
0 1
1 2
1 5

Sample Output

1
2
3
Case 1: 1
Case 2: 3
Case 3: 6

Solution

很明顯是一個等比級數的計算，中間牽涉到除法，利用費馬小定理找到乘法反元素，藉此完成除法。

特別記住，V 只得是 degree 而搜尋樹的分支數，因此 degree 會包含跟父親的連接。特別小心 V = 1 的情況，要不兩個點要不一個點，而 V = 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>
#include <assert.h>
const long long mod = 1000000007LL;
long long mul(long long a, long long b) {
    long long ret = 0;
    for( ; b != 0 ; b>>=1, (a<<=1)%=mod)
        if(b&1)
            (ret += a) %= mod;
    return ret;
}
long long mpow(long long x, long long y, long long mod) {
    long long ret = 1;
    while (y) {
        if (y&1)
            ret = (ret * x)%mod;
        y >>= 1LL, x = (x * x)%mod;
    }
    return ret;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int testcase, cases = 0;
    long long D, V;
    scanf("%d", &testcase);
    while (scanf("%lld %lld", &D, &V) == 2) {
        assert(D >= 0 && V > 0 && D <= 2e+9 && V <= 2e+9);
        long long ret = 0;
        if (D == 0)			ret = 1;
        else if (D == 1)	ret = (V + 1)%mod;
        else if (V == 1)	ret = -1;
        else if (V == 2)	ret = (1 + D * 2)%mod;
        else {
            ret = mpow(V - 1, D, mod) - 1 + mod;
            ret = ret * mpow(V - 2, mod - 2, mod) %mod;
            ret = ret * V %mod;
            ret = (ret + 1 + mod)%mod;
            assert(ret >= 0);
        }
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
/*
1000
0 1
1 2
1 5
500 1
0 500
2000000000 2000000000
*/
Read More +
解題區/解題區 - UVa

UVa 10186 - Euro Cup 2000

Problem

給定 N 個隊伍，兩兩隊伍比賽兩次，已知部分比賽結果，勝者得三分，平手各得一分，輸者 零分。請問在剩餘比賽中，每個隊伍的最佳排名與最糟排名。

重點：剩下的比賽最多十場。

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
2
A
B
1
A B 1 0
5
Ger
Tur
Fin
Nor
Mol
14
Fin Mol 3 2
Tur Nor 3 0
Tur Ger 1 0
Nor Fin 1 0
Mol Ger 1 3
Tur Fin 1 3
Nor Mol 2 2
Nor Ger 0 3
Tur Mol 2 0
Ger Fin 2 0
Mol Fin 0 0
Ger Mol 6 1
Fin Tur 2 4
Mol Nor 0 0
0

Sample Output

1
2
3
4
5
6
7
8
9
10
Group #1
A 1-2
B 1-2
Group #2
Ger 1-3
Tur 1-3
Fin 1-4
Nor 1-5
Mol 4-5

Solution

一開始以為題目只給我 10 場資訊，結果一直想不到 P 的解法，只有 10 場就直接窮舉 10 場的結果紀錄即可。

額外閱讀 Matrix67 网络流和棒球赛淘汰问题

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 <string.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int g[32][32] = {}, score[32], n;
int brank[32], wrank[32];
vector< pair<int, int> > game;
void dfs(int idx) {
    if (idx == game.size()) {
        vector< pair<int, int> > board;
        int r;
        for (int i = 0; i < n; i++)
            board.push_back(make_pair(score[i], i));
        sort(board.begin(), board.end(), greater< pair<int, int> >());
        for (int i = 0; i < n; i++) {
            r = (int)(lower_bound(board.begin(), board.end(), make_pair(score[i], 0x3f3f3f3f), greater< pair<int, int> >()) 
                        - board.begin());
            brank[i] = min(brank[i], r);
            r = (int)(upper_bound(board.begin(), board.end(), make_pair(score[i], -1), greater< pair<int, int> >()) 
                        - board.begin());
            wrank[i] = max(wrank[i], r);
        }
        return ;
    }
    int x = game[idx].first, y = game[idx].second;
    score[x] += 3;
    dfs(idx+1);
    score[x] -= 3;
    
    score[y] += 3;
    dfs(idx+1);
    score[y] -= 3;
    
    score[x]++, score[y]++;
    dfs(idx+1);
    score[x]--, score[y]--;
}
int main() {
    char s[128];
    int cases = 0;
    int m, x, y, a, b;
    string name[128];
    while (scanf("%d", &n) == 1 && n) {
        map<string, int> R;
        memset(g, 0, sizeof(g));
        memset(score, 0, sizeof(score));
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            R[s] = i, name[i] = s;
        }
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%s", s);
            x = R[s];
            scanf("%s", s);
            y = R[s];
            g[x][y]++, g[y][x]++;
            scanf("%d %d", &a, &b);
            if (a < b)		score[y] += 3;
            else if (a > b)	score[x] += 3;
            else			score[x]++, score[y]++;
        }
        
        for (int i = 0; i < n; i++)
            brank[i] = 0x3f3f3f3f, wrank[i] = -1;
        game.clear();
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                for (int k = 0; k < 2 - g[i][j]; k++) {
                    game.push_back(make_pair(i, j));
                }
            }
        }
        dfs(0);
        printf("Group #%d\n", ++cases);
        for (int i = 0; i < n; i++) {
            printf("%s %d-%d\n", name[i].c_str(), brank[i] + 1, wrank[i]);
        }
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10185 - Phylogenetic Trees Inherited

Problem

給 n 個化合物，每個化合物長度 m。其中 n 為 2 的冪次。

建造一個分類的關係樹，每一個節點上會有分類依據長度依舊為 m，而每一個化合物按照輸入順序成為完滿樹的葉節點。

目標這個樹的花費越少越好，樹花費的計算為相鄰兩個節點之間的漢明碼距離總和。也就是與子節點所表示的字串之間有多少不同的字符。

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
31
32
33
34
35
36
4 3
AAG
AAA
GGA
AGA
  
4 3
AAG
AGA
AAA
GGA 
  
4 3
AAG
GGA
AAA
AGA
  
4 1
A
R
A
R
  
2 1
W
W
  
2 1
W
Y
  
1 1
Q
  
0 0

Sample Output

1
2
3
4
5
6
7
AGA 3
AGA 4
AGA 4
R 2
W 0
Y 1
Q 0

Solution

事實上，我們可以分開考慮 m 位的結果，彼此之間的花費最小化即可。

當只考慮要填什麼的時候，如果兩個子樹填法有所交集，則表示選擇其中一個，與其子節點都不需要花費，如果是空集，則必然選擇其中一個子樹結果來補足，花費多 1。

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
#include <stdio.h>
char acid[1024][1024], ret[2048];
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2 && n) {
        for (int i = 0; i < n; i++)
            scanf("%s", acid[i]);
        ret[m] = '\0';
        int diff = 0, N = 2 * n;
        for (int i = 0; i < m; i++) {
            int dp[2048] = {};
            for (int j = n; j < N; j++)
                dp[j] = 1<<(acid[j - n][i] - 'A');
            for (int j = n-1; j > 0; j--) {
                dp[j] = dp[j<<1]&dp[j<<1|1];
                if (dp[j] == 0) { // choose one branch, cost 1
                    diff++;
                    dp[j] = dp[j<<1]|dp[j<<1|1];
                }
            }
            for (int j = 0; j < 26; j++) {
                if ((dp[1]>>j)&1) {
                    ret[i] = j + 'A';
                    break;
                }
            }
        }
        printf("%s %d\n", ret, diff);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10184 - Equidistance

Problem

在地球上，給定許多地點的經緯度，兩個人必須在中立領域中見面，兩個人分別在球面上的兩個點，中立領域則是兩點連線的中點，垂直拉出的一個大圓 (球體上的一圈)。

它們現在位於地球上某點，請問到大圓的最短距離為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Ulm             48.700 10.500
Freiburg        47.700 9.500
Philadelphia    39.883 -75.250
SanJose         37.366 -121.933
Atlanta         33     -84
Eindhoven       52     6
Orlando         28     -82
Vancouver       49     -123
Honolulu        22     -157
NorthPole       90     0
SouthPole       -90    0
#
Ulm Freiburg Philadelphia
SanJose Atlanta Eindhoven
Orlando Vancouver Honolulu
NorthPole SouthPole NorthPole
Ulm SanDiego Orlando
NorthPole SouthPole SouthPole
Ulm Honolulu SouthPole
#

Sample Output

1
2
3
4
5
6
7
Philadelphia is 690 km off Ulm/Freiburg equidistance.
Eindhoven is 3117 km off SanJose/Atlanta equidistance.
Honolulu is 4251 km off Orlando/Vancouver equidistance.
NorthPole is 10019 km off NorthPole/SouthPole equidistance.
Orlando is ? km off Ulm/SanDiego equidistance.
SouthPole is 10019 km off NorthPole/SouthPole equidistance.
SouthPole is 1494 km off Ulm/Honolulu equidistance.

Solution

特別小心，詢問的兩點相同，導致整個球體都是中立領域。

對於球體找到圓的最短距離，找出夾角即可。

首先拉出 AB 線，將其移動至眼前水平放置 (O A B 同一水平面)，又 OM 會於 AB 中點拉出來的大圓夾角 theta (直接 AB 和 OM 內積得角度)，此時的大圓應該是垂直 90 度，藉此得到最短距離。

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <map>
using namespace std;
struct Point {
    double x, y, z;
    Point(double a=0, double b=0, double c=0):
        x(a), y(b), z(c) {}
    Point operator-(const Point &a) const {
        return Point(x - a.x, y - a.y, z - a.z);
    }
    double len() {
        return sqrt(x * x + y * y + z * z);
    }
};
int main() {
    const double pi = acos(-1);
    const double earth_r = 6378;
    char s[1024], s2[1024], s3[1024];
    double lat, lon; //  latitude, longitude
    map<string, Point> R;
    while (scanf("%s", s) == 1) {
        if (!strcmp(s, "#"))
            break;
        scanf("%lf %lf", &lat, &lon);
        lat = lat * pi / 180.0;
        lon = lon * pi / 180.0;
        double x, y, z;
        x = earth_r * cos(lat) * cos(lon);
        y = earth_r * cos(lat) * sin(lon);
        z = earth_r * sin(lat);
        R[s] = Point(x, y, z);
    }
    while (scanf("%s", s) == 1) {
        if (!strcmp(s, "#"))
            break;
        scanf("%s %s", s2, s3);
        if (R.find(s) == R.end() || R.find(s2) == R.end() || R.find(s3) == R.end()) {
            printf("%s is ? km off %s/%s equidistance.\n", s3, s, s2);
        } else {
            Point A = R[s], B = R[s2], M = R[s3];
            Point AB = A - B, OM = M;
            double dot = AB.x * OM.x + AB.y * OM.y + AB.z * OM.z;
            double theta = acos(fabs(dot) / AB.len() / OM.len());
            double ret = (pi /2 - theta) * earth_r;
#define eps 1e-6
            if (fabs(AB.x) < eps && fabs(AB.y) < eps && fabs(AB.z) < eps)
                ret = 0;
            printf("%s is %.0lf km off %s/%s equidistance.\n", s3, ret, s, s2);
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1031 - Insecure in Prague

Problem

給一段密文，輸出最長的明文，如果最長明文有多個，則輸出 Codeword not unique。

加密的工序為

  • 決定四個參數 s, t, i, j
  • 類似殺人遊戲般，一開始有 m 個空位，初始位置於 s 開始數，每 i 個空位就填入明文的下一個字符。
  • 然後重複動作填入第二次明文，但是起始位置 t，每 j 個空位填入。
  • 剩餘位置隨機填入字符。

Sample Input

1
2
3
4
APPURAAURGEGEWE
ABABABAB
THEACMPROGRAMMINGCONTEST
X

Sample Output

1
2
3
Code 1: PRAGUE
Code 2: Codeword not unique
Code 3: Codeword not unique

Solution

題目中有一段

Starting with the first empty slot in or after position t in string …

看起來 t 一點也不重要。也就是不用特定對 t 窮舉參數，將每個可以填入的位置都嘗試過當初始位置。

窮舉的順序，窮舉 s, n, i 可以在第一次填入工序中，得到明文結果。然後在第二步處理中，檢查是否明文填入時時候對應到原本的密文。

在窮舉前，可以事先計算殺人遊戲的殺戮順序，好在窮舉時得到明文結果。在第二步窮舉時，由於已經將部分明文填入好，剩餘的空格少了快一半，必須將其壓縮再一起，重新使用殺人遊戲的填入方式。

這一題很卡常數，很優化就優化，寫到眼神崩盤。

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <stdio.h>
#include <string.h>
#include <set>
#include <iostream>
#include <vector>
using namespace std;
vector<int> putOrder[51][51]; // [m][i]
int main() {
    for (int m = 2; m < 50; m++) {
        for (int i = 0; i < m; i++) {
            int visited[50] = {}, pos = 0, skip = 0;
            putOrder[m][i].push_back(pos), visited[pos] = 1;
            for (int p = 1; p < m; p++) {
                skip = i % (m - p);
                while (skip >= 0) {
                    pos++;
                    if (pos >= m)	pos = 0;
                    if (!visited[pos])
                        skip--;
                }
                visited[pos] = 1;
                putOrder[m][i].push_back(pos);
            }
        }
    }
//	for (int i = 0; i < putOrder[15][6].size(); i++) // example
//		printf("%d\n", (putOrder[15][6][i] + 1)%15);
    char text[64];
    int cases = 0;
    while (gets(text)) {
        if (!strcmp("X", text))	break;
        int m = strlen(text);
        int appear[128] = {};
        for (int i = 0; text[i]; i++)
            appear[text[i]]++;
            
        int mxlen = 1, remainUsed[64];
        set<string> ret[64];
        for (int s = m-1; s >= 0; s--) {
            if (appear[text[s]] < 2) // must not start alphabet			
                continue;
            for (int n = m/2; n >= mxlen; n--) {
                if (ret[n].size() > 1)	continue;
                char plain[128];
                for (int i = 0; i < m; i++) {
                    if (ret[n].size() > 1)	continue;
                    int cnt[128] = {}, used[64] = {};
                    int ok = 1;
                    for (int p = 0; p < putOrder[m][i].size() && p < n; p++)
                        plain[p] = text[(putOrder[m][i][p] + s)%m], used[(putOrder[m][i][p] + s)%m] = 1;
                    plain[n] = '\0';
                    for (int p = 0; p < n; p++) {
                        cnt[plain[p]]++;
                        if (cnt[plain[p]] * 2 > appear[plain[p]])
                            ok = 0;
                    }
                    if (!ok)	continue;
                    if (ret[n].find(plain) != ret[n].end())
                        continue;
                        
                    int mm = 0;
                    for (int p = 0; p < m; p++) {
                        if (!used[p])
                            remainUsed[mm++] = p;
                    }
                    for (int t = 0; t < mm; t++) {
                        if (plain[0] != text[remainUsed[t]])	
                            continue;
                        if (ret[n].size() > 1)	continue;
                        for (int j = i + 1; j < m; j++) {
                            if (ret[n].size() > 1)	continue;
                            int visited[50] = {};
                            int pos = t, skip = 0, ok2 = 1;
                            visited[pos] = 1;
                            for (int p = 1; p < n; p++) {
                                skip = j % (mm - p);
                                while (skip >= 0) {
                                    pos++;
                                    if (pos >= mm)	pos = 0;
                                    if (!visited[pos])
                                        skip--;
                                }
                                if (plain[p] != text[remainUsed[pos]]) {
                                    ok2 = 0;
                                    break;
                                }
                                visited[pos] = 1;
                            }
                            if (ok2) {
                                if (n > mxlen)
                                    mxlen = n;
                                ret[n].insert(plain);
                            }
                        }
                    }
                }
            }
        }
        printf("Code %d: ", ++cases);
        for (int i = m/2; i >= 0; i--) {
            if (ret[i].size()) {
                if (ret[i].size() == 1)
                    printf("%s\n", ret[i].begin()->c_str());
                else
                    puts("Codeword not unique");
                break;
            }
        }
    }
    return 0;
}
/*
APPURAAURGEGEWE
ABABABAB
THEACMPROGRAMMINGCONTEST
X
*/
Read More +
解題區/解題區 - UVa

UVa 1029 - Heliport

Problem

逆時針順序給定一個正交多邊形，請問內接最大圓為何？

Sample Input

1
2
3
4
5
4
2 R 2 U 2 L 2 D
10
10 R 10 U 10 L 10 U 10 R 5 U 30 L 20 D 20 R 5 D
0

Sample Output

1
2
3
Case Number 1 radius is: 1.00
Case Number 2 radius is: 10.00

Solution

首先，這題不能模擬退火，至少我的技巧退火沒結果。

於是二分最大圓半徑，接著窮舉所有可能匹配的圓，針對圓檢查是否包含於正交多邊形內部。

決定半徑之後，圓心存在於幾種可能

  • 通過圓上的兩點，可以決定兩個圓心。
  • 兩條線相切於圓，可以決定四個圓心。
  • 交一點、切一線，可以決定兩個圓心。

首先必須檢測圓心是否在正交多邊形中，用了射線法莫名其妙 WA，所以建議特別考慮於正交多邊形的內部判定。隨後檢查所有線段不會部分或全部在圓內部。

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <math.h>
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;
        if (fabs(y-a.y) > eps)
            return y < a.y;
        return false;
    }
    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);
    }
    void read() {
        scanf("%lf %lf", &x, &y);
    }
};
struct Seg {
    Pt s, e;
    Seg(Pt a = Pt(), Pt b = Pt()):
        s(a), e(b) {}
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.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);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if(cross(as, at, bs) * cross(as, at, bt) < 0 &&
       cross(at, as, bs) * cross(at, as, bt) < 0 &&
       cross(bs, bt, as) * cross(bs, bt, at) < 0 &&
       cross(bt, bs, as) * cross(bt, bs, at) < 0)
        return 1;
    return 0;
}
double distProjection(Pt as, Pt at, Pt s) {
    int a, b, c;
    a = at.y - as.y;
    b = as.x - at.x;
    c = - (a * as.x + b * as.y);
    return fabs(a * s.x + b * s.y + c) / hypot(a, b);
}
double ptToSeg(Seg seg, Pt p) {
    double c = 1e+30;
    if(between(seg.s, seg.e, p))
        c = min(c, distProjection(seg.s, seg.e, p));
    else
        c = min(c, min(dist(seg.s, p), dist(seg.e, p)));
    return c;
}
int inPolygon(Pt p[], int n, Pt q) {
    int i, j, cnt = 0;
    for(i = 0, j = n-1; i < n; j = i++) {
        if(onSeg(q, p[i], p[j]))
            return 1;
        if(p[i].y > q.y != p[j].y > q.y &&
           q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
           cnt++;
    }
    return cnt&1;
}
// this problem
Pt D[1024];
int N;
int checkCircle(double x, double y, double r) {
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        if (D[i].x > x && (D[i].y > y != D[i+1].y > y))
            cnt++;
    }
    if (cnt%2 == 0)	return 0;
    for (int i = 0; i < N; i++) {
        if ((D[i].x - x) * (D[i].x - x) + (D[i].y - y) * (D[i].y - y) < (r - eps)* (r - eps))
            return 0;
        if (D[i].x == D[i + 1].x && (D[i].y > y != D[i+1].y > y) && fabs(D[i].x - x) < r - eps)
            return 0;
        if (D[i].y == D[i + 1].y && (D[i].x > x != D[i+1].x > x) && fabs(D[i].y - y) < r - eps)
            return 0;
    }
    return 1;
}
int checkRadius(double r) {
    for (int i = 0; i < N; i++) {
        if (D[i].x == D[i+1].x)
        for (int j = 0; j < N; j++) {
            if (D[j].y == D[j+1].y) {
                if (checkCircle(D[i].x + r, D[j].y + r, r))
                    return 1;
                if (checkCircle(D[i].x + r, D[j].y - r, r))
                    return 1;
                if (checkCircle(D[i].x - r, D[j].y + r, r))
                    return 1;
                if (checkCircle(D[i].x - r, D[j].y - r, r))
                    return 1;
            }
        }
    }
    
    double d, dd, dx, dy, x, y;
    for (int i = 0; i < N; i++) { // (line, point) => circle
        for (int j = 0; j < N; j++) {
            if (D[i].x == D[i+1].x) {
                d = fabs(D[j].x - (D[i].x + r));
                if (d < r) {
                    dy = sqrt(r*r - d*d);
                    if (checkCircle(D[i].x + r, D[j].y + dy, r))
                        return 1;
                    if (checkCircle(D[i].x + r, D[j].y - dy, r))
                        return 1;
                }
                d = fabs(D[j].x - (D[i].x - r));
                if (d < r) {
                    dy = sqrt(r*r - d*d);
                    if (checkCircle(D[i].x - r, D[j].y + dy, r))
                        return 1;
                    if (checkCircle(D[i].x - r, D[j].y - dy, r))
                        return 1;
                }
            } else {
                d = fabs(D[j].y - (D[i].y + r));
                if (d < r) {
                    dx = sqrt(r*r - d*d);
                    if (checkCircle(D[j].x + dx, D[i].y + r, r))
                        return 1;
                    if (checkCircle(D[j].x - dx, D[i].y + r, r))
                        return 1;
                }
                d = fabs(D[j].y - (D[i].y - r));
                if (d < r) {
                    dx = sqrt(r*r - d*d);
                    if (checkCircle(D[j].x + dx, D[i].y - r, r))
                        return 1;
                    if (checkCircle(D[j].x - dx, D[i].y - r, r))
                        return 1;
                }
            }
        }
    }
    
    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            x = (D[i].x + D[j].x)/2;
            y = (D[i].y + D[j].y)/2;
            d = hypot(x - D[i].x, y - D[i].y);
            if (d < r) {
                dd = sqrt(r*r - d*d);
                dx = (y - D[i].y)/d * dd;
                dy = (D[i].x - x)/d * dd;
                
                if (checkCircle(x + dx, y + dy, r))
                    return 1;
                if (checkCircle(x - dx, y - dy, r))
                    return 1;
            }
        }
    }
    return 0;
}
int main() {
    int n, x, cases = 0;
    char cmd[1024];
    const int dx[] = {1, 0, -1, 0};
    const int dy[] = {0, 1, 0, -1};
    int R[128];
    R['R'] = 0, R['U'] = 1, R['L'] = 2, R['D'] = 3;
    while(scanf("%d", &n) == 1 && n) {
    	D[0] = Pt(0, 0), N = n;
    	for (int i = 1; i <= n; i++) {
    		scanf("%d %s", &x, cmd);
    		D[i].x = D[i-1].x + x * dx[R[cmd[0]]];
    		D[i].y = D[i-1].y + x * dy[R[cmd[0]]];
    	}
    	double l = 0, r = 1000, ret, mid;
    	while (fabs(l - r) > eps) {
    		mid = (l + r)/2;
    		if (checkRadius(mid))
    			l = mid, ret = mid;
    		else
    			r = mid;
    	}
    	if (cases)	puts("");
    	printf("Case Number %d radius is: %.2lf\n", ++cases, ret);
    }
    return 0;
}
/*
4
2 R 2 U 2 L 2 D
10
10 R 10 U 10 L 10 U 10 R 5 U 30 L 20 D 20 R 5 D
12
1 R 1 U 1 R 1 U 1 L 1 U
1 L 1 D 1 L 1 D 1 R 1 D
 */
Read More +
解題區/解題區 - UVa

UVa 1008 - A Vexing Problem

Problem

給予一個 Vexed! 遊戲，這遊戲類似於消球遊戲，可以左右拖動特定元素使其掉落，在一個瞬間中可以讓相鄰兩個相同元素同時消失。在下一個瞬間，仍在盤面上的元素會根據重力往下墜落，如果又發現存有相同元素相鄰，則會不斷地迭代消去。

請問如何在最少步數下把所有元素消去。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
4 5 SAMPLE-01
#A--#
##-B#
#AB##
#####
6 7 SAMPLE-02
#--Y--#
#-ZX-X#
#-##-##
#-XZ--#
####YZ#
#######
0 0 END

Sample Output

1
2
3
4
5
6
SAMPLE-01: Minimum solution length = 2
(B,1,3,L) (A,0,1,R)
SAMPLE-02: Minimum solution length = 9
(Y,0,3,R) (Z,4,5,L) (X,1,3,R) (Z,1,2,R)
(Z,1,3,R) (X,3,4,R) (X,3,2,R) (X,4,5,L)
(X,1,5,L)

Solution

對於每一個盤面做紀錄，並且對於每一個元素嘗試是否能向左向右拉動，拉動之後將其模擬墜落相消的過程。使用 bfs 的方式進行路徑搜索，隨後回溯即可。

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include <stdio.h>
#include <string.h>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
#define hash_mod 1000003
int n, m, visited[16][16], cases = 0;
struct State {
    char g[10][10];
    int label;
    bool operator<(const State &x) const {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (g[i][j] != x.g[i][j])
                    return g[i][j] < x.g[i][j];
        return false;
    }
    unsigned int hash() {
        unsigned int a = 63689, b = 378551;
        unsigned int value = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                value = value * a + g[i][j];
                a *= b;
            }
        }
        return value % hash_mod;
    }
    int dfs(int x, int y, char c) {
        if (x < 0 || y < 0 || x >= n || y >= m)
            return 0;
        if (g[x][y] != c || visited[x][y] == cases)
            return 0;
        visited[x][y] = cases;
        int ret = 0;
        ret += dfs(x+1, y, c);
        ret += dfs(x, y+1, c);
        ret += dfs(x-1, y, c);
        ret += dfs(x, y-1, c);
        return 1 + ret;
    }
    void erase(int x, int y, int c) {
        if (x < 0 || y < 0 || x >= n || y >= m)
            return ;
        if (g[x][y] != c || visited[x][y] != cases)
            return ;
        g[x][y] = '-';
        erase(x+1, y, c);
        erase(x, y+1, c);
        erase(x-1, y, c);
        erase(x, y-1, c);
    }
    void fall() {
        for (int i = n-1; i >= 0; i--) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] >= 'A' && g[i][j] <= 'Z') {
                    int k = i+1;
                    while (k < n && g[k][j] == '-') {
                        g[k][j] = g[k-1][j];
                        g[k-1][j] = '-';
                        k++;
                    }
                }
            }
        }
    }
    void refresh() {
        int update = 0, cnt;
        do {
            fall();
            update = 0;
            memset(visited, 0, sizeof(visited));
            cases = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (visited[i][j] == 0 && g[i][j] >= 'A' && g[i][j] <= 'Z') {
                        cases++;
                        cnt = dfs(i, j, g[i][j]);
                        if (cnt > 1)
                            erase(i, j, g[i][j]), update = 1;
                    }
                }
            }
        } while (update);
    }
    int isCompleted() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                if (g[i][j] >= 'A' && g[i][j] <= 'Z')
                    return 0;
        }
        return 1;
    }
};
struct Info {
    int x, y, dir, prev;
    char c;
    Info(int s1 = 0, int s2 = 0, int s3 = 0, int s4 = 0, char s = 0):
        x(s1), y(s2), dir(s3), prev(s4), c(s) {
    }
};
map<State, int> R[hash_mod];
vector<Info> history;
int main() {
    char casesName[105];
    State st, next;
    int h, step;
    while (scanf("%d %d %s", &n, &m, casesName) == 3 && n) {
        for (int i = 0; i < n; i++)
            scanf("%s", &st.g[i]);
        history.resize(1);
        for (int i = 0; i < hash_mod; i++)
            R[i].clear();
        
        int labelCnt = 0, label;
        queue<State> Q;
        st.refresh(), st.label = 0;		
        h = st.hash();
        R[h][st] = 0, Q.push(st);
        while (!Q.empty()) {
            st = Q.front(), Q.pop();
            h = st.hash(), label = st.label;
            step = R[h][st];
            if (st.isCompleted())
                break;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (st.g[i][j] >= 'A' && st.g[i][j] <= 'Z') {
                        if (j+1 < m && st.g[i][j+1] == '-') {
                            next = st;
                            swap(next.g[i][j], next.g[i][j+1]);
                            next.refresh();
                            h = next.hash();
                            if (R[h].find(next) == R[h].end()) {
                                next.label = ++labelCnt;
                                history.push_back(Info(i, j, 1, label, st.g[i][j]));
                                R[h][next] = step + 1;
                                Q.push(next);
                            }
                        }
                        if (j-1 >= 0 && st.g[i][j-1] == '-') {
                            next = st;
                            swap(next.g[i][j], next.g[i][j-1]);
                            next.refresh();
                            h = next.hash();
                            if (R[h].find(next) == R[h].end()) {
                                next.label = ++labelCnt;
                                history.push_back(Info(i, j, 0, label, st.g[i][j]));
                                R[h][next] = step + 1;
                                Q.push(next);
                            }
                        }
                    }
                }
            }
        }
        printf("%s: Minimum solution length = %d\n", casesName, step);
        int idx = st.label;
        vector<Info> ret;
        while (idx) {
            ret.push_back(history[idx]);
            idx = history[idx].prev;
        }
        for (int i = ret.size() - 1, j = 0; i >= 0; i--, j++) {
            if (j%4)	putchar(' ');
            printf("(%c,%d,%d,%c)", ret[i].c, ret[i].x, ret[i].y, ret[i].dir ? 'R' : 'L');
            if (j%4 == 3)	puts("");
        }
        if (ret.size()%4)	puts("");
    }
    return 0;
}
Read More +
解題區/出題解題

[ACM 題目] 竹馬不敵天降

Problem

「話說，剛剛明明說的是合乎聖誕節的商品。這不是 H-GAME 嗎？哪裡有聖誕元素啊！」
「嗯，真虧你發現這點啊，但還是有點可惜，這是全齡版，沒有工口哦！」
「不管怎麼樣，一點也沒合聖誕節啊。」
「雖然你有好好學習許多東西，但對本質上完全沒有理解。」
「最近開始覺得有點明白了 …」
「那麼就來說明下這個作品吧」
「是一年前發售的大人氣美少女遊戲的續篇吧？」
「是的，那為什麼你沒有察覺到－『一年前』這句話所包含的意義」
「對於期盼著的人那就意味著 … 與戀人時隔一年的再會！」

在 GALGAME 故事發展過程中，竹馬幾乎沒勝過天降，走哪一條線進行發展正是玩 GALGAME 的樂趣。

然而有一款極為糟糕的 GALGAME 的初始方式則是在一開始選定座標下，系統會根據座標找到附近最鄰近少女，並且在隨後的故事情節都會圍繞這名少女。

遊戲的地圖設計很簡單，用一個矩形表示，現在已知 N 名少女的所在地 (都在矩形內部)。一開始選定的座標也必須落在矩形內，請問玩哪每個線路機率分布為何？

Input

輸入有多組測資。

每組第一行會有三個整數 N, A, B，表示在$[0:A] \times [0:B]$ 地圖中有 N 個已知座標。
接下來會有 N 行，每行上會有兩個整數 x, y，表示每名少女所在的座標$(x, y)$ 保證不會有重疊的情況。

$(0 < N \le 100, 0 < A, B \le 1000, 0 \le x \le A, 0 \le y \le B)$

Output

對於每組測資輸出一行，根據輸入順序輸出每一個故事線的機率。

Sample Input

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

Sample Output

1
2
3
Case 1: 0.500 0.500
Case 2: 0.300 0.700
Case 3: 0.292 0.313 0.396

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6 
#define MAXN 32767
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
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);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
        angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > -eps)
            return true;
        return false;
    }
};
Pt getIntersect(Seg a, Seg b) {
    double a1, b1, c1, a2, b2, c2;
    double dx, dy, d;
    a1 = a.s.y - a.e.y, b1 = a.e.x - a.s.x;
    c1 = a1 * a.s.x + b1 * a.s.y;
    a2 = b.s.y - b.e.y, b2 = b.e.x - b.s.x;
    c2 = a2 * b.s.x + b2 * b.s.y;
    dx = c1 * b2 - c2 * b1, dy = a1 * c2 - a2 * c1;
    d = a1 * b2 - a2 * b1;
    return Pt(dx/d, dy/d);
}
Seg deq[MAXN];
vector<Pt> halfPlaneIntersect(vector<Seg> segs) {
    sort(segs.begin(), segs.end());
    int n = segs.size(), m = 1;
    int front = 0, rear = -1;
    for (int i = 1; i < n; i++) {
        if (fabs(segs[i].angle - segs[m-1].angle) > eps)
            segs[m++] = segs[i];
    }
    n = m;
    deq[++rear] = segs[0];
    deq[++rear] = segs[1];
    for (int i = 2; i < n; i++) {
        while (front < rear && cross(segs[i].s, segs[i].e, getIntersect(deq[rear], deq[rear-1])) < -eps)
            rear--;
        while (front < rear && cross(segs[i].s, segs[i].e, getIntersect(deq[front], deq[front+1])) < -eps)
            front++;
        deq[++rear] = segs[i];
    }
    while (front < rear && cross(deq[front].s, deq[front].e, getIntersect(deq[rear], deq[rear-1])) < -eps)
        rear--;  
    while (front < rear && cross(deq[rear].s, deq[rear].e, getIntersect(deq[front], deq[front+1])) < -eps)
    	front++;
    	
    vector<Pt> ret;
    for (int i = front; i < rear; i++) {
        Pt p = getIntersect(deq[i], deq[i+1]);
        ret.push_back(p);
    }
    if (rear > front + 1) {
        Pt p = getIntersect(deq[front], deq[rear]);
        ret.push_back(p);
    } 
    return ret;
}
double calc_convexarea(const vector<Pt> &p) {
    double ret = 0;
    int n = p.size();
    for(int i = 0, j = n - 1; i < n; j = i++)
        ret += p[j].x * p[i].y - p[j].y * p[i].x;
    return fabs(ret /2.0);
}
int main() {
    int n, A, B, cases = 0;
    Pt p[128], mid, vij;
    while (scanf("%d %d %d", &n, &A, &B) == 3) {
        for (int i = 0; i < n; i++)
            scanf("%lf %lf", &p[i].x, &p[i].y);
        printf("Case %d:", ++cases);
        for (int i = 0; i < n; i++) {
            int m = 0;
            vector<Seg> segs;
            segs.resize(n - 1 + 4);
            for (int j = 0; j < n; j++) {
                if (i == j)	continue;
                mid.x = (p[i].x + p[j].x) /2.0;
                mid.y = (p[i].y + p[j].y) /2.0;
                vij.x = mid.x - (p[j].y - p[i].y);
                vij.y = mid.y + (p[j].x - p[i].x);
                segs[m] = Seg(mid, vij), m++;
            }
            segs[m++] = Seg(Pt(0, 0), Pt(A, 0));
            segs[m++] = Seg(Pt(A, 0), Pt(A, B));
            segs[m++] = Seg(Pt(A, B), Pt(0, B));
            segs[m++] = Seg(Pt(0, B), Pt(0, 0));
            vector<Pt> convex = halfPlaneIntersect(segs);
//			for (int j = 0; j < convex.size(); j++)
//				printf("%lf %lf\n", convex[j].x, convex[j].y);
//			puts("--");
            printf(" %.3lf", calc_convexarea(convex) / (A * B));
        }
        puts("");
    }
    return 0;
}
/*
2 5 3
1 2
4 2
2 5 3
1 1
2 2
3 5 3
1 1
2 2
4 1
*/
Read More +
解題區/解題區 - UVa

UVa 11985 - Prime Independence

Problem

給 N 個數字，找到最大子集滿足任 A, B 數字，A 不為 B 的質數倍。

Sample Input

1
2
3
4
5
6
7
3
5
2 4 8 16 32
5
2 3 4 6 9
3
1 2 3

Sample Output

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

Solution

看起來就是一個二分圖找最大獨立集，但是建造的速度要夠快，少說也要 500 ms，然後在二分匹配上必須採用很快速的最大流，這裡採用 dinic 版本，網路上搜索到這個版本挺不錯的。

為了遇見妳，已經撒了無數 TLE。
求到妳接受的那個瞬間，神啊！謝謝祢的禮物才讓我們相遇。

對於最大流算法，一般而言會經過不斷地溯洄沖減， Dinic 分層圖的方式進行計算，但是可以利用指針對於每個節點進行記錄，在沖減時，對指針結果的下一條邊進行計算，而不對於每一個點的所有邊重頭來過。

接著，分層圖可以利用沖減時，進行計算，即當找到瓶頸時，更新該點的層次。取代一般重新使用 bfs 的分層計算。

最大獨立集 = 點數 - 最大匹配數。

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <assert.h>
#include <set>
using namespace std;
const int MAXV = 40010;
const int MAXE = MAXV * 200 * 2;
const int INF = 1<<29;
typedef struct Edge {
    int v, cap, flow;
    Edge *next, *re;
} Edge;
class MaxFlow {
    public:
    Edge edge[MAXE], *adj[MAXV], *pre[MAXV], *arc[MAXV];
    int e, n, level[MAXV], lvCnt[MAXV], Q[MAXV];
    void Init(int x) {
        n = x, e = 0;
        for (int i = 0; i < n; ++i) adj[i] = NULL;
    }
    void Addedge(int x, int y, int flow){
        edge[e].v = y, edge[e].cap = flow, edge[e].next = adj[x];
        edge[e].re = &edge[e+1], adj[x] = &edge[e++];
        edge[e].v = x, edge[e].cap = 0, edge[e].next = adj[y];
        edge[e].re = &edge[e-1], adj[y] = &edge[e++];
    }
    void Bfs(int v){
        int front = 0, rear = 0, r = 0, dis = 0;
        for (int i = 0; i < n; ++i) level[i] = n, lvCnt[i] = 0;
        level[v] = 0, ++lvCnt[0];
        Q[rear++] = v;
        while (front != rear){
            if (front == r) ++dis, r = rear;
            v = Q[front++];
            for (Edge *i = adj[v]; i != NULL; i = i->next) {
                int t = i->v;
                if (level[t] == n) level[t] = dis, Q[rear++] = t, ++lvCnt[dis];
            }
        }
    }
    int Maxflow(int s, int t){
        int ret = 0, i, j;
        Bfs(t);
        for (i = 0; i < n; ++i) pre[i] = NULL, arc[i] = adj[i];
        for (i = 0; i < e; ++i) edge[i].flow = edge[i].cap;
        i = s;
        while (level[s] < n){
            while (arc[i] && (level[i] != level[arc[i]->v]+1 || !arc[i]->flow)) 
                arc[i] = arc[i]->next;
            if (arc[i]){
                j = arc[i]->v;
                pre[j] = arc[i];
                i = j;
                if (i == t){
                    int update = INF;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        if (update > p->flow) update = p->flow;
                    ret += update;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        p->flow -= update, p->re->flow += update;
                    i = s;
                }
            }
            else{
                int depth = n-1;
                for (Edge *p = adj[i]; p != NULL; p = p->next)
                    if (p->flow && depth > level[p->v]) depth = level[p->v];
                if (--lvCnt[level[i]] == 0) return ret;
                level[i] = depth+1;
                ++lvCnt[level[i]];
                arc[i] = adj[i];
                if (i != s) i = pre[i]->re->v;
            }
        }
        return ret;
    }
} g;
#define MAXL (500000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[MAXL];
int P[100000], Pt = 0;
vector<int> pfactor[524288];
int A[MAXV], RE[524288], XY[524288];
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 500000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            XY[i] = 1;
//			for(k = n/i, j = i*k; k >= i; k--, j -= i)
//				SET(j);
            for (j = i+i; j <= n; j += i)
                SET(j), XY[j] = XY[j/i] + 1, pfactor[j].push_back(i);
            pfactor[i].push_back(i);
            P[Pt++] = i;
        }
    }
}
int main() {
    sieve();
    int testcase, cases = 0;
    int n, x;
    scanf("%d", &testcase);
    while (testcase--) {
   		scanf("%d", &n);
   		memset(RE, -1, sizeof(RE));
   		for (int i = 0; i < n; i++) {
   			scanf("%d", &A[i]);
   			RE[A[i]] = i;
   		}
   		g.Init(n + 2);
   		int source = n, sink = n + 1;
   		for (int i = 0; i < n; i++) {
   			if (XY[A[i]]&1)
   				g.Addedge(source, i, 1);
   			else
   				g.Addedge(i, sink, 1);
   			for (int j = 0; j < pfactor[A[i]].size(); j++) {
   				int y = A[i] / pfactor[A[i]][j];
   				if (RE[y] != -1) {
   					if (XY[y]&1)
   						g.Addedge(RE[y], i, 1);
   					else
   						g.Addedge(i, RE[y], 1);
   				}
   			}
   		}
   		printf("Case %d: %d\n", ++cases, n - g.Maxflow(source, sink));
   	}
    return 0;
}
/*
3
5
2 4 8 16 32
5
2 3 4 6 9
3
1 2 3
1000
3
7 35 105
*/
Read More +