Gym 101673F Keeping On Track（搜索）

Keeping On Track

Acmar and Ibmar are at war! You are in charge of a rail network that transports important supplies throughout the great state of Acmar during this delicate time. The rail system is made up of a set of rail lines which meet at various junction points. While there is no limit to the number of rail lines that can meet at a junction, the network is set up so that there is only one path between any two junctions. You’ve tried to argue for some redundancy in the system, i.e., extra rail lines so that there are two or more paths connecting some junctions, but it’s wartime and budgets are tight.

However, this may soon change as you’ve just been given some terrible news from double agents working in Ibmar: within the next month enemy spies plan to blow up one of the junctions! Unfortunately, the exact junction is not known, but knowing your enemy well you are certain that they will undoubtedly strike the critical junction, specifically the junction whose removal disconnects the most pairs of other remaining junctions in the system. You don’t have much time to act, so the most you can do is add one new line connecting two currently unconnected junctions, thereby reducing the number of disconnected pairs after the critical junction has been destroyed. Your job is to determine how to make the number of disconnected pairs as small as possible by adding in the best possible rail line.

Input

Input starts with a line containing an integer n (2≤n≤10000) indicating the number of rail lines in the system. Following that are n lines of the form i2 indicating that a rail line connects junctions i1 and i2. Junctions are numbered consecutively starting at 0. All rail lines are two-way and no rail line appears more than once in the input. There is exactly one path between any two junction points given in the input.

Output

Display two values n1n1 and n2n2, where n1n1 is the number of pairs of junctions which will be disconnected when the enemy destroys the critical junction, and n2n2 is the number of pairs of junctions still disconnected after you add in the best possible rail line. There will never be more than one critical junction.

Sample Input 1

Sample Output 1

11 5

Sample Input 2

2
2 1
0 1

Sample Output 2

1 0

链接

https://cn.vjudge.net/problem/Gym-101673F

题意

n+1个点n条边(点的标号从0开始)的无向图，定义关键点为删除该点后使得剩余的节点中不连通的点对的数量最多的结点，保证只存在一个关键点。现有两个问题：

删除关键点后不连通的节点对的数量
在两点之间添加一条边，使得删除关键点后剩余节点中不连通的节点对的数量尽可能少，问最少的数量

题解

我们可以枚举每个点作为关键点，然后统计第一个问题的答案，只需要一遍dfs，统计的时候进行更新；第二问就是在第一问的基础之上，把剩余的连通块中两个点数最多的连通块连在一起，这样得到的就是最优解。
参考了题解：传送门

代码

Status	Accepted
Time	30ms
Memory	752kB
Length	2113

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 10010;
int n, tot, head[maxn], cccnt[maxn], id, ans1, ans2;

struct Edge
{
    int to, next;
}edge[maxn<<2];

void init()
{
    ans1 = ans2 = tot = id = 0;
    memset(head, -1, sizeof(head));
}

void addedge(int u, int v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

void dfs1(int u, int fa)
{
    cccnt[u] = 1; // 以u为根节点的连通分量点数，初始化为1
    vector <int> V; // 保存去除点u后剩余连通分量的点数
    int sum = 0; // 记录以u为根节点的子节点的总数
    for (int i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].to;
        if (v == fa)
            continue;
        dfs1(v, u);
        V.push_back(cccnt[v]); // 子节点连通分量点数
        sum += cccnt[v];
        cccnt[u] += cccnt[v];
    }
    V.push_back(n - sum); // 剩余的一个连通分量点数
    int t = 0, s = 0;
    for (int i = 0; i < V.size(); ++i) // 求出去除u结点的一组解
    {
        t += s * V[i];
        s += V[i];
    }
    if (t > ans1) // 更新
    {
        ans1 = t;
        id = u;
    }
}

void dfs2(int u, int fa)
{
    cccnt[u] = 1;
    for (int i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].to;
        if (v == fa)
            continue;
        dfs2(v, u);
        cccnt[u] += cccnt[v];
    }
}

int main()
{
    int u, v;
    scanf("%d", &n);
    init();
    for (int i = 0; i < n; ++i)
    {
        scanf("%d%d", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    dfs1(0, -1);
    dfs2(id, -1); // 关键点作为根节点进行dfs得到每个连通分量
    vector <int> V;
    for (int i = head[id]; i != -1; i = edge[i].next)
    {
        int v = edge[i].to;
        V.push_back(cccnt[v]);
    }
    if (V.size() == 1) // 删完关键点后依然是一个连通分量
        printf("0 0\n");
    else
    {
        sort(V.begin(), V.end());
        V[V.size()-2] += V[V.size()-1]; // 将最大的两个连通块连在一起
        int t = 0, s = 0;
        for (int i = 0; i < V.size() - 1; ++i)
        {
            t += s * V[i];
            s += V[i];
        }
        ans2 = t;
        printf("%d %d\n", ans1, ans2);
    }
    return 0;
}

一开始还以为是无向图点求割点什么的，涉及点双连通分量，没想到只需要两遍dfs就能求出结果。

The end.
2018-08-15 星期三