Connecting Two Barns (USACO Silver 2021 December)

Connecting Two Barns (USACO Silver 2021 December)

题意：NN个点MM条边的无向图，可以以(i−j)2(i-j)^2的代价任意增加两条边，问使得11和NN连通的最小代价。

就是三种情况之一：

  1. 11和NN本来就通
  2. 11和NN的连通分量之间加一条边
  3. 找到某个连通分量，分别向11和NN各加一条边。

找出所有连通分量是O(N)\mathcal{O}(N)的操作（DFS）。然后，因为题目定义的这个(i−j)2(i-j)^2代价，一个连图分量到一个点的最小距离是可以(O)(log⁡N)\mathcal(O)(\log N)算出来的，就是下面程序中的distance()。

有了以上信息之后，我们遍历所有节点，分别计算到11和NN的连通分量的最小距离，就可以滚动求每个连通分量到11和NN的最小距离，从而一遍扫描解决问题。O(Nlog⁡N)\mathcal{O}(N \log N)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int T;
int n, m, a, b;
vector<int> adj[100005];
int cc[100005];         // connected component is marked by a number, the barns with the same 
                        // number are in the same connected component
ll dist1[100005];       // min distance to cc of barn 1
ll distn[100005];       // min distance to cc of barn N
 
// bool isadj[100005];  
int cur;
void dfs(int x, int cur){
    cc[x] = cur;
    for (int y : adj[x]) {
        if (cc[y] == -1)
            dfs(y, cur);
    }
}
 
// binary search to find the minimum distance from barn x to a sorted list of barns
ll distance(vector<int> &barns, int x) {
    ll r = 1e18;
    auto it = lower_bound(barns.begin(), barns.end(), x);
    if (it != barns.end()) {
        // if (*it == x) return 0;
        r = min(r, (ll)(*it - x) * (*it - x));
    }
    if (it != barns.begin()) {
        r = min(r, (ll)(x - *(it-1)) * (x - *(it-1)));
    }
    return r;
}
 
int main(){
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        for(int i=0; i<=n; i++){
            adj[i].clear();
            cc[i]=-1;
            dist1[i]=distn[i]=1e18;
        }
        for(int i=0; i<m; i++){
            scanf("%d %d", &a, &b);
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        // now mark all connected components with DFS,  O(N)
        cur = 0;
        for(int i=1; i<=n; i++){
            if (cc[i]==-1)
                dfs(i, cur);
                cur++;
            }
 
        if (cc[1] == cc[n]) {
            printf("0\n");
            continue;
        }
 
        vector<int> barns1, barnsn;
        for (int i = 1; i <= n; i++) {
            if (cc[i] == cc[1]) barns1.push_back(i);
            if (cc[i] == cc[n]) barnsn.push_back(i);
        }  
 
        ll ans=1e18;        // (10^5)^2, so use long long
        for (int i = 1; i <= n; i++) {
            int x = cc[i];
            dist1[x] = min(dist1[x], distance(barns1, i));
            distn[x] = min(distn[x], distance(barnsn, i));
            ans = min(ans, dist1[x] + distn[x]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}