UVa 10765 Doves and bombs 鸽子和炸弹的故事——求割点

一打开这道题，我不禁吓了一跳。。。超长的题目还带一张图，这种满篇文字的题目不禁让人感觉压抑。而且很有ACM出题的风范，下面我摘录一小段：

1
It is the year 95 ACM (After the Crash of Microsoft). After many years of peace, a war has broken out. Your nation, the island of Evergreen Macros And Confusing Shortcuts (EMACS), is defending itself against the railway empire ruled by Visually Impaired Machinists (VIM).

这就是ACM的题目里面十分常见的一个景象——扩充缩写。这件事情是这么干的：已知一个缩写，比如ACM，我们找出一些词汇，让它们表达出一个含义，并且它的缩写是ACM，就像上文做的那样——After the Crash of Microsoft.

有的时候，这件事情是很有意思的。出题的人也许是给我们这些做题的人在思考题目的过程中带来一些有趣的东西。不过对于我这种英语苦手来说。。。。。。我才不喜欢这样的题目呢。

好像说的有点跑题。不过这个题目本身还是很简单的。

题目定义了“鸽子度”这个东西，它就是一张图中去掉一个点之后剩下的连通分支个数。

题目求的是“鸽子度”最大而序号最低的前m个点，并把这些点的序号和“鸽子度”输出。

我从东京大学ACM模板上面抄了一份神代码并且把它转换成了C++11的代码，这种存储一张图的格式十分值得借鉴。

AC代码如下：

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 <iostream> 
#include <algorithm> 
#include <string> 
#include <vector> 
using namespace std; 

class V : public vector<int> { 
public: 
    int index; 
    int num, count; 
    V(int idx = 0) :index(idx), num(-1), count(0) { 

    } 
    bool operator < (const V &b) const { 
        if (count != b.count){ 
            return count > b.count; 
        } 
        else{ 
            return index < b.index; 
        } 
    } 
}; 
int dfs(vector<V> &vs, V &v, int c) { 
    v.num = c; 
    int low = c; 
    for (int u : v) { 
        if (vs[u].num < 0) { 
            int t = dfs(vs, vs[u], c + 1); 
            low = min(low, t); 
            if (v.num <= t) v.count++; 
        } else low = min(low, vs[u].num); 
    } 
    return low; 
} 
void solve(int n, int m){ 
    vector<V> vs; 
    for (int i = 0; i < n; i++){ 
        vs.push_back(V(i)); 
    } 
    int x, y; 
    while (cin >> x >> y){ 
        if (x < 0 && y < 0) break; 
        vs[x].push_back(y); 
        vs[y].push_back(x); 
    } 
    for (vector<V>::iterator it = vs.begin(); it != vs.end(); it++){ 
        if ((*it).num < 0){ 
            dfs(vs, *it, 0); 
            if ((*it).count > 0){ 
                (*it).count--; 
            } 
        } 
    } 
    sort(vs.begin(), vs.end()); 
    for (int i = 0; i < m; i++){ 
        cout << vs[i].index << ' ' << vs[i].count + 1 << 'n'; 
    } 
} 
int main(int agrc, char *agrv[]){ 
    ios::sync_with_stdio(false); 
    int n, m; 
    while (cin >> n >> m, n m){ 
        solve(n, m); 
        cout << 'n'; 
    } 
}