Code Festival 2016 Final G Zigzag MST

边的数量是无限的，考虑如何减少边的数量。

对于一次加边 $(a, b, c)$ ，注意到加边后形成了一条链，并且权值在不断增加。考虑克鲁斯卡尔算法的过程，先将所有的边排序，然后考虑是否选择，在考虑链上的一条边的时候，前面的点都已经形成一个连通块了，因此对于一条边，可以任意将起点接在前面的任意一个点上，而答案是不变的。现在我们要考虑如何使得重边尽可能多，这样实际有效的边就会更少。可以发现，参与这条链的点，依次为 $a, b, a + 1, b + 1, \ldots , $ ,考虑将 $a _ i$ 接在 $a _ {i - 1}$ 上，那么可以形成一条环，很多边都重合，同时还有一条边 $(a, b, c)$ 。对于这个环上的点，记 $s _ i$ 表示 $i$ 和 $i - 1$ 的边，每次更新，只更新两条边，最后推一次即可。

另外附上官方题解，上面的图很形象。

查看代码

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
template <class Type>
void read (Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write (Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar('0' + x % 10);
}
template <class Type>
void chkmin (Type &x, Type k)
{
    k < x && (x = k);
}
typedef long long LL;
const int N = 2e5 + 10, inf = 2e9;
LL s[N];
int n, m, p[N];
int fa (int x)
{
    return p[x] == x ? x : p[x] = fa(p[x]);
}
struct Edge
{
    int u, v;
    LL w;
    bool operator < (const Edge &_) const
    {
        return w < _.w;
    }
};
vector <Edge> e;
int main ()
{
    read(n), read(m);
    for (int i = 0; i < n; i++)
        s[i] = inf;
    for (int a, b, c; m; m--)
    {
        read(a), read(b), read(c);
        chkmin(s[a], c + 1ll), chkmin(s[b], c + 2ll);   
        e.push_back((Edge){a, b, c});
    }
    LL t = s[0];
    for (int i = 0; i < n << 1; i++, t += 2)
        chkmin(t, s[i % n]), chkmin(s[i % n], t);
    for (int i = 0; i < n; i++)
        e.push_back((Edge){i, (i + 1) % n, s[i]});
    sort(e.begin(), e.end());
    for (int i = 0; i < n; i++)
        p[i] = i;
    LL res = 0;
    for (Edge i : e)
        if (fa(i.u) ^ fa(i.v))
        {
            res += i.w;
            p[p[i.u]] = p[i.v];
        }
    write(res);
    return 0;
}