[POI 2010] TEL-Teleportation题解

· · 题解

很好的题目，使我大脑旋转。

看起来没有那么难，但其实还是很考验思维的。

solution

先把题意转化一下，问向给定的无向图内最多加多少条边，使得点 1 到点 2 的最短路边数仍大于等于 5。

直接加不好操作，所以我们转换成用加完边的图的边数减去原来的边得到答案。

考虑将图分成五层，每一层分别有这些点（为了便于理解，没有按顺序给出）：

考虑还能在哪里加边。

显然每一层可以和同层的所有点连边，并且可以保证最短路边数不变。

对于第一层的点显然不能向其他层加边，如果加了就会缩短最短路边数。对于第五层也是如此。

对于第二层的点，它已经和第一层连边，也不能和第四、第五层连边，如果连边就会缩短最短路边数。它可能已经和第三层连边，也可能没有。对于是否可以和第三层连边，我们放在第三层考虑。同样对于第四层也是如此。

对于第三层，它由这些点组成：

题目保证原图中点 1 到点 2 的最短路边数大于等于 5，所以第三层只由这些点组成。

和第二层直接相连的点可以和第二层所有的点都连一条边，这样可以保证最短路边数不变。同样，对于和第四层直接相连的点，也可以向第四层所有的点连一条边。对于孤立点，可以向第二层和第四层中点数更多的那一侧连边。不可以同时向第二层和第四层连边，因为会导致最短路边数小于 5。

:::info[为何这样是最优的？] 已经证明，除第三层外其他层不能向外连边。显然第三层不能向第一、第五层连边，只能向第二、第四层其中一层连边。所以向可以连边的层中点数最多的层连边就是最优解。 :::

code

我的思路比较清晰，但是我的代码比较冗长，凑合看吧。

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define debug(x) cerr<<"debug "<<__LINE__<<":"<<#x<<" = "<<x<<"\n"
#define For(i,a,b) for(int i = a;i<=b;i++)
inline ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){f=-1;}c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return f*x;}
inline void write(ll x){if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+'0');}
using namespace std;
vector<int> g[40005];
pii s[1000005];
int f[8][8],h[40005],cnt2,cnt3,cnt4;
int main(){
    int n = read(),m = read();
    For(i,1,m){
        int u = read(),v = read();
        g[u].push_back(v);
        g[v].push_back(u);
        s[i] = {u,v};
    }
    h[1] = 1;
    h[2] = 5;
    For(i,1,m){
        if(s[i].first == 1) h[s[i].second] = 2,cnt2++,f[1][2]++;
        else if(s[i].second == 1) h[s[i].first] = 2,cnt2++,f[1][2]++;
        else if(s[i].first == 2) h[s[i].second] = 4,cnt4++,f[4][5]++;
        else if(s[i].second == 2) h[s[i].first] = 4,cnt4++,f[4][5]++;
    }
    For(i,1,n) if(h[i] == 0) h[i] = 3,cnt3++;
    For(i,1,m){
        if((h[s[i].first] == 2 && h[s[i].second] == 3)||(h[s[i].first] == 3 && h[s[i].second] == 2)) f[2][3]++;
        if((h[s[i].first] == 4 && h[s[i].second] == 3)||(h[s[i].first] == 3 && h[s[i].second] == 4)) f[3][4]++;
        if((h[s[i].first] == 3 && h[s[i].second] == 3)) f[3][3]++;
        if((h[s[i].first] == 2 && h[s[i].second] == 2)) f[2][2]++;
        if((h[s[i].first] == 4 && h[s[i].second] == 4)) f[4][4]++;
    }
    ll ans = 0;
    For(i,1,n){
        if(h[i]!=3) continue;
        int c2 = 0,c4 = 0;
        for(auto it:g[i]){
            if(h[it] == 2) c2++;
            if(h[it] == 4) c4++;
        }
        if(c2>0){
            ans+=cnt2-c2;
        }
        else if(c4>0) ans+=cnt4-c4;
        else ans+=max(cnt2,cnt4);
    }
    write(cnt2*(cnt2-1)/2-f[2][2]+cnt4*(cnt4-1)/2-f[4][4]+cnt3*(cnt3-1)/2-f[3][3]+ans);
    return 0;
}

//据说玛兹在须弥有「智慧」的意思，如此精致玲珑的「智慧」，着实令人无法抗拒。

//纳西妲的眼里有着温柔的笑意：「海葵帮助并见证了鱼儿成长，鱼儿的小小馈赠也是理所应当的呀。」