解題區/解題區 - UVa

UVa 12017 - Imitation

contents

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

Problem

遞移性 a->b, b->c 則 a->c。

給定一張圖的遞移，求不改變任兩個點的遞移關係，最多可以有多少邊、最少需要多少條邊。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
3
3 3
1 2
2 3
1 3
3 3
1 2
2 3
3 1
9 9
1 2
2 3
3 1
4 5
5 6
6 4
7 8
8 9
9 7

Sample Output

1
2
3
Case #1: 2 3
Case #2: 3 6
Case #3: 9 18

Solution

從最多條邊來說，最簡單使用 floyd 內閉包的算法 O(n^3)。

1
2
3
4
for k in n
    for i in n
        for j in n
            f[i, j] |= f[i][k] & f[k][j]

最後計算 1(true) 的個數即可，但是這一題 n 最大為 1000，必須從 O(n^3) -> O(n^2)，取而代之，採用 dfs 的方式，把每一個點 s 當作起點，則可以搜索到的點 t，都存有遞移關係 s->t。

而在處理最少條邊，採用強連通元件 (SCC)，先將數個點縮成一個元件，則一個強連通元件內的個數只需要使用一個環即可代替原先的遞移關係。縮圖完之後，會產生 DAG 圖，DAG 圖上仍然會有多餘的遞移關係，從 a->b, b->c, a->c 中，可以發現 a->c 可以不存在。

最後，採用 bfs 的方式，對於每個點 s 當作起點找到最長路徑，假使 t 距離 s 大於 1，且存在 s->t，則可以再少一條邊。

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
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
vector<int> g[1005], dag[1005];
int vfind[1005], findIdx;
int stk[1005], stkIdx;
int in_stk[1005], visited[1005];
int contract[1005], contract_cnt[1005];
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]) {
        contract_cnt[nd] = 0;
        do {
            in_stk[stk[stkIdx]] = 0;
            contract[stk[stkIdx]] = nd;
            contract_cnt[nd]++;
        } while(stk[stkIdx--] != nd);
    }
    return mn;
}
int min_edge, max_edge, mg[1024][1024];
void dfs(int u, int start) {
    mg[start][u] = 1, max_edge++;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (!mg[start][v]) {
            dfs(v, start);
        }
    }
}
void bfs(int st, int n) {
    queue<int> Q;
    int dist[1024] = {}, u, v;
    Q.push(st);
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        for (int i = 0; i < dag[u].size(); i++) {
            v = dag[u][i];
            if (dist[v] < min(dist[u] + 1, 2)) {
                dist[v] = min(dist[u] + 1, 2);
                Q.push(v);
            }
        }
    }
    for (int i = 0; i < dag[st].size(); i++) {
        int v = dag[st][i];
//        printf("%d %d %d\n", st, v, dist[v]);
        if (dist[v] != 1) {
            if (mg[st][v]) {
                mg[st][v] = 0, min_edge--;
            }
        }
    }
}
int main() {
    int testcase, cases = 0, n, m;
    int u, v;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i <= n; i++)
            g[i].clear(), dag[i].clear();
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
        }
        min_edge = max_edge = 0;
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= n; j++)
                mg[i][j] = 0;
        
        for (int i = 1; i <= n; i++)
            dfs(i, i);
        
        // SCC
        memset(visited, 0, sizeof(visited));
        memset(in_stk, 0, sizeof(in_stk));
        for(int i = 1; i <= n; i++) {
            if(!visited[i]) {
                findIdx = stkIdx = 0;
                scc(i);
            }
        }
        
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= n; j++)
                mg[i][j] = 0;
        
        for(int i = 1; i <= n; i++) {
            int x = contract[i], y;
            for(vector<int>::iterator it = g[i].begin();
                it != g[i].end(); it++) {
                y = contract[*it];
                if(x != y) {
                    if (!mg[x][y]) {
                        mg[x][y] = 1, dag[x].push_back(y);
                        min_edge++;
                    }
                }
            }
        }
        
        for (int i = 1; i <= n; i++) {
            if (contract[i] == i) {
                if (contract_cnt[i] > 1)
                    min_edge += contract_cnt[i];
                bfs(i, n);
            }
        }
        printf("Case #%d: %d %d\n", ++cases, min_edge, max_edge - n);
    }
    return 0;
}
/*
 3
 3 3
 1 2
 2 3
 1 3
 3 3
 1 2
 2 3
 3 1
 9 9
 1 2
 2 3
 3 1
 4 5
 5 6
 6 4
 7 8
 8 9
 9 7
 */