2010-1122

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目大意：每个点和边都有权值。点是本来就有的，边是从最开始一条都没有按题目给的顺序每一年增加一条的。现在有一个人要从0点出发，走遍所有其他点（可以走多次）最后回到0点。问对于对于每一年是否能制定出一个在一年内走完的计划，并求花费。每经过一条边则花费对应的权值，每到一个点则花费对应权值。

解法：题目有一个条件是那个人只能有N-1条路的通行证，又要到所有的节点，所以整个图是一棵树的结构。很容易知道在一棵树上，从一个点出发走遍所有点再回来，则每个点被访问的次数等于这个点的度，而且每条边被访问两次。所以点的权值可以分配到相邻的边上。于是就是求一棵树使得边权之和最小，即MST。但是这题中原图的边不断增加，因此需要动态维护MST。

我们假设某一时刻的MST或（所有节点还未全部联通时的）森林已经算出来了，现在增加了一条边，使之构成了环。则通过dfs找到环中最大的边并且删掉它即可。另外还要注意闰年导致该年天数增加1的问题。

复杂度：如果通过并查集判联通，则每加一条边需要O(n)地dfs一次。因此复杂度是O(nm)。

{{{
#!cpp
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
#include <cassert>

using namespace std;

const int MAXN = 205;

int n, m, x, y, maxlen;
int t1[MAXN];
map <int, int> e[MAXN];
bool used[MAXN];

int p[MAXN];
inline int findp(int k) {
    if (p[k] == k) {
        return k;
    } else {
        return p[k] = findp(p[k]);
    }
}

inline void setFriend(int i, int j) {
    p[findp(i)] = findp(j);
}

inline bool isFriend(int i, int j) {
    return findp(i) == findp(j);
}

void init() {
    for (int i = 0; i < n; i++) {
        e[i].clear();
        p[i] = i;
    }
}

void dfs(int u, int v, int _x, int _y, int len) {
    if (u == v) {
        x = _x;
        y = _y;
        maxlen = len;
        return;
    }
    for (map <int, int>::const_iterator it = e[u].begin(); it != e[u].end(); it++) {
        if (used[it->first]) {
            continue;
        }
        used[it->first] = true;
        if (it->second > len) {
            dfs(it->first, v, u, it->first, it->second);
        } else {
            dfs(it->first, v, _x, _y, len);
        }
        if (maxlen != -1) {
            return;
        }
    }
}

int isleap(int year) {
    return ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) ? 1 : 0;
}

int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        init();
        for (int i = 0; i < n; i++) {
            scanf("%d", &t1[i]);
            t1[i] *= 24;
        }
        int res = 0;
        int edgeCount = 0;
        for (int i = 0; i < m; i++) {
            int u, v, t;
            scanf("%d%d%d", &u, &v, &t);
            t = t * 2 + t1[u] + t1[v];
            if (isFriend(u, v)) {
                x = y = maxlen = -1;
                memset(used, 0, sizeof(used));
                used[u] = true;
                dfs(u, v, -1, -1, -1);
                if (maxlen > t) {
                    res = res - maxlen + t;
                    e[x].erase(y);
                    e[y].erase(x);
                    e[u][v] = e[v][u] = t;
                }
            } else {
                e[u][v] = e[v][u] = t;
                res += t;
                edgeCount++;
                setFriend(u, v);
            }
            if (edgeCount == n - 1 && res <= 24 * (365 + isleap(1000 + i))) {
                printf("%.2lf\n", fabs(res / 24.0));
            } else {
                printf("-1\n");
            }
        }
        printf("\n");
    }
    return 0;
}
}}}

题目大意：每个点和边都有权值。点是本来就有的，边是从最开始一条都没有按题目给的顺序每一年增加一条的。现在有一个人要从0点出发，走遍所有其他点（可以走多次）最后回到0点。问对于对于每一年是否能制定出一个在一年内走完的计划，并求花费。每经过一条边则花费对应的权值，每到一个点则花费对应权值。

解法：题目有一个条件是那个人只能有N-1条路的通行证，又要到所有的节点，所以整个图是一棵树的结构。很容易知道在一棵树上，从一个点出发走遍所有点再回来，则每个点被访问的次数等于这个点的度，而且每条边被访问两次。所以点的权值可以分配到相邻的边上。于是就是求一棵树使得边权之和最小，即MST。但是这题中原图的边不断增加，因此需要动态维护MST。

我们假设某一时刻的MST或（所有节点还未全部联通时的）森林已经算出来了，现在增加了一条边，使之构成了环。则通过dfs找到环中最大的边并且删掉它即可。另外还要注意闰年导致该年天数增加1的问题。

复杂度：如果通过并查集判联通，则每加一条边需要O(n)地dfs一次。因此复杂度是O(nm)。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
#include <cassert>
using namespace std;
const int MAXN = 205;
int n, m, x, y, maxlen;
int t1[MAXN];
map <int, int> e[MAXN];
bool used[MAXN];
int p[MAXN];
inline int findp(int k) {
    if (p[k] == k) {
        return k;
    } else {
        return p[k] = findp(p[k]);
    }
}
inline void setFriend(int i, int j) {
    p[findp(i)] = findp(j);
}
inline bool isFriend(int i, int j) {
    return findp(i) == findp(j);
}
void init() {
    for (int i = 0; i < n; i++) {
        e[i].clear();
        p[i] = i;
    }
}
void dfs(int u, int v, int _x, int _y, int len) {
    if (u == v) {
        x = _x;
        y = _y;
        maxlen = len;
        return;
    }
    for (map <int, int>::const_iterator it = e[u].begin(); it != e[u].end(); it++) {
        if (used[it->first]) {
            continue;
        }
        used[it->first] = true;
        if (it->second > len) {
            dfs(it->first, v, u, it->first, it->second);
        } else {
            dfs(it->first, v, _x, _y, len);
        }
        if (maxlen != -1) {
            return;
        }
    }
}
int isleap(int year) {
    return ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) ? 1 : 0;
}
int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        init();
        for (int i = 0; i < n; i++) {
            scanf("%d", &t1[i]);
            t1[i] *= 24;
        }
        int res = 0;
        int edgeCount = 0;
        for (int i = 0; i < m; i++) {
            int u, v, t;
            scanf("%d%d%d", &u, &v, &t);
            t = t * 2 + t1[u] + t1[v];
            if (isFriend(u, v)) {
                x = y = maxlen = -1;
                memset(used, 0, sizeof(used));
                used[u] = true;
                dfs(u, v, -1, -1, -1);
                if (maxlen > t) {
                    res = res - maxlen + t;
                    e[x].erase(y);
                    e[y].erase(x);
                    e[u][v] = e[v][u] = t;
                }
            } else {
                e[u][v] = e[v][u] = t;
                res += t;
                edgeCount++;
                setFriend(u, v);
            }
            if (edgeCount == n - 1 && res <= 24 * (365 + isleap(1000 + i))) {
                printf("%.2lf\n", fabs(res / 24.0));
            } else {
                printf("-1\n");
            }
        }
        printf("\n");
    }
    return 0;
}