[POI2010]TEL-Teleportation

因为题目中要求 \(1 \sim 2\) 的最短路只有 \(5\)，于是我们可以考虑直接使用人脑将图分层。

那么我们怎么定义每层的点呢？因为要使 \(1 \sim 2\) 的最短路只有 \(5\)，我们可以将最终的图分为 \(6\) 层，分别为距离 \(1\) 号距离为 \(0, 1, 2, 3, 4, 5\) 的点。但是最开始的这张图并不是所有点都能划分到这些层里面去，但是我们可以对原图先划分好必定在某些层内的点。首先 \(1\) 肯定是划分在 \(0\) 层，和 \(1\) 相邻的点肯定是划分在 \(1\) 层，除 \(1, 2\) 层以外和 \(1\) 层相邻的点肯定是划分在 \(2\) 层。同理 \(2\) 一定是划分在第 \(5\) 层的，而和 \(2\) 相邻的点（除了 \(0, 1, 2\) 层外）肯定会被划分在第 \(4\) 层，除了 \(0, 1, 2, 4, 5\) 层外的点和 \(4\) 层相邻的点肯定会被划分在第 \(3\) 层。那么原始图的分层就已经分完了，为了让能连的边尽可能的多，我们一定是要将没被划分的点通过连边让他被划分，而划分的点要尽可能和其他已经划分的点连边。

先考虑简单的部分，已经分层的点怎样连边不会有问题。可以发现我们在同一层内两两连边是没有问题的，因此同一层内的点我们可以连成完全图。其次，对于相邻层的点我们也可以互相连边也不会出现问题。但是如果我们对不相邻的两个层数之间连边，就会让最短路 \(-1\) 而不合法，因此我们在已经分层的点中间连边只能将同层连成完全图和将相邻层互相连边。

再来考虑如何将剩下的点划分，下面我们令已经分好层的部分第 \(i\) 层的点数为 \(cnt_i\)，点 \(j\) 已经和第 \(i\) 层相连的数量为 \(c_{j, i}\)。可以发现没有被划分的点一定是仅和第 \(2, 3\) 层连边的点，其次每个点一定是会被划分到 \(2, 3\) 层的，证明的话可以考虑每个点划分进某个层的增量，如果要划分入第 \(1\) 层，增量将会是 \(1 + cnt_2 - c_{i, 2}\)，如果划分入第 \(2\) 层，那么增量将会是 \(cnt_1 + cnt_2 - c_{i, 2}\)，因此划分入第 \(2\) 层一定是比划分入第 \(1\) 更优的，同理划分入 \(3\) 一定是比 \(4\) 优的。于是我们只需要考虑将每个点划分进第 \(2\) 层或第 \(3\) 层。如果划分进第二层，那么增量为 \(cnt_1 + cnt_2 - c_{i, 2} + cnt_3 - c_{i, 3}\)；如果划分进第三层，那么增量为 \(cnt_4 + cnt_2 - c_{i, 2} + cnt_3 - c_{i, 3}\)，可以发现影响大小关系的只有 \(cnt_1, cnt_4\)，因此如果 \(cnt_1\) 更大我们放入 \(2\) 层，如果 \(cnt_4\) 更大我们放入 \(3\) 层，因为 \(cnt_1, cnt_4\) 的大小是没有变的，因此每个点的决策都将是一致的，于是我们只需统计每层有多少个点再连边即可。

代码实现时一些变量名可能和上面的讲述不同。

#include<bits/stdc++.h>

using namespace std;

#define N 1000000 + 5

#define rep(i, l, r) for(int i = l; i <= r; ++i)

#define Next(i, u) for(int i = h[u]; i; i = e[i].next)

struct edge{

    int v, next;

}e[N << 1];

int n, m, u, v, tot, ans, cnt[N], h[N], col[N];

int read(){

    char c; int x = 0, f = 1;

    c = getchar();

    while(c > '9' || c < '0'){ if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

void add(int u, int v){

    e[++tot].v = v, e[tot].next = h[u], h[u] = tot;

    e[++tot].v = u, e[tot].next = h[v], h[v] = tot;

}

int C(int n){

    return n * (n - 1) / 2;

}

int main(){

    n = read(), m = read();

    rep(i, 1, m) u = read(), v = read(), add(u, v);

    Next(i, 1) col[e[i].v] = 1;

    Next(i, 2) col[e[i].v] = 2;

    rep(i, 1, n){

        if(col[i] == 1){

            Next(j, i) if(!col[e[j].v] && e[j].v != 1 && e[j].v != 2) col[e[j].v] = 3;

        }

        if(col[i] == 2){

            Next(j, i) if(!col[e[j].v] && e[j].v != 1 && e[j].v != 2) col[e[j].v] = 4;

        }

    }

    rep(i, 3, n) if(!col[i]) col[i] = 5;

    rep(i, 1, n) ++cnt[col[i]];

    ans = cnt[1] + cnt[2] + C(cnt[1]) + C(cnt[2]);

    if(cnt[1] > cnt[2]) ans += C(cnt[3] + cnt[5]) + C(cnt[4]) + (cnt[1] + cnt[4]) * (cnt[3] + cnt[5]) + cnt[2] * cnt[4];

    else ans += C(cnt[3]) + C(cnt[4] + cnt[5]) + (cnt[5] + cnt[4]) * (cnt[3] + cnt[2]) + cnt[1] * cnt[3];

    printf("%d\n", ans - m);

    return 0;

}

巴特西

[POI2010]TEL-Teleportation

最新文章

热门文章