2021 高階競程 Contest #6 - 題解

懶惰的旅人

• Task Provider: D4nnyLee
• Task Setter: D4nnyLee

首殺 team21_24 (00:04)

解法說明

這題因為道路的長度都是大於

$0$，所以其實

$x_i$ 就只是與

$i$ 之間有直達道路的所有城市中最近的那個城市。

標準程式

#include <iostream>
#include <vector>
using namespace std;

constexpr int inf{1000000010};

int main(void) {
    int n, m;
    cin >> n >> m;
    
    vector<pair<int, int>> ans(n, {inf, -1});
    for (int i{0}; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        
        --u, --v;
        if (w < ans[v].first)
            ans[v] = {w, u};
        if (w < ans[u].first)
            ans[u] = {w, v};
    }
    
    for (int i{0}; i < n; ++i)
        cout << ans[i].second + 1 << ' ';
    cout << '\n';
    return 0;
}

踏溯成大

• Task Provider: arashi87
• Task Setter: arashi87

首殺 team21_24 (00:33)

解法說明

知道圖會是一棵樹後就會知道這題不能用單純的最短路通過，我們可以知道樹上最短路會唯一，因此假設我們要找

$x,y$ 的最短路徑的話可以先找出

$x$ 到根節點以及

$y$ 到根節點的距離相加，最後再扣掉

$2\times dis(LCA(x,y))$ 就會是答案，扣兩次的原因是因為

$LCA(x,y)$ 到根節點這段被重複算到兩次，它並不會被包含在最短路裡，因此需要扣掉，距離計算的部分則是可以在 dfs 時同步完成。

標準程式

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

class LCA {
    const vector<vector<pair<int, long long>>>& adj;
    int n;
    vector<int> d;
    vector<int> log2;
    vector<vector<int>> an{};
    void dfs(int u, int w = -1, int dep = 0) {
        d[u] = dep;
        an[u][0] = w;
        for (int i{1}; i <= log2[n - 1] && an[u][i - 1] != -1; ++i)
            an[u][i] = an[an[u][i - 1]][i - 1]; // 走 2^(i-1) 再走 2^(i-1) 步
        
        // 因為計算 an 會用到祖先的資訊，所以先計算再繼續往下
        for (auto& [v, _] : adj[u]) {
            if (v == w) continue; // parent
            dfs(v, u, dep + 1);
        }
    }
public:
    LCA(const vector<vector<pair<int, long long>>>& _adj, int root)
    : adj{_adj}, n{adj.size()}, d(n), log2(n) {
        log2[1] = 0;
        for (int i{2}; i < log2.size(); ++i) log2[i] = log2[i / 2] + 1;
        an.assign(n, vector<int>(log2[n - 1] + 1, -1));
        dfs(root);
    }
    int operator()(int u, int v) {
        if (d[u] > d[v]) swap(u, v);

        for (int i{log2[d[v] - d[u]]}; i >= 0; --i)
            if (d[v] - d[u] >= (1 << i)) v = an[v][i];
        // v 先走到跟 u 同高度
        if (u == v) return u;
    
        for (int i{log2[d[u]]}; i >= 0; --i)
            if (an[u][i] != an[v][i]) u = an[u][i], v = an[v][i];
        // u, v 一起走到 lca(u, v) 的下方

        return an[u][0];
        // 回傳 lca(u, v)
    }
};

class DIS {
    const vector<vector<pair<int, long long>>>& adj;
    int n;
    vector<long long> dis;
    void dfs(int u, int w = -1, long long d = 0) {
        dis[u] = d;
        for (auto& [v, len] : adj[u]) {
            if (v == w) continue;
            dfs(v, u, d + len);
        }
    }
public:
    DIS(const vector<vector<pair<int, long long>>>& _adj, int root) : adj{_adj}, n{adj.size()}, dis(n) {
        dfs(root);
    }
    long long operator()(int v) {
        return dis[v];
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, long long>>> adj(n);
    for (int i{0}; i < n - 1; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w, --u, --v;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    int r{0};
    LCA lca{adj, r};
    DIS dis{adj, r};

    while (m--) {
        int u, v;
        cin >> u >> v, --u, --v;
        cout << dis(u) + dis(v) - 2 * dis(lca(u, v)) << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t{1};
    //cin >> t;
    while (t--) solve();

    return 0;
}

紅心 7 的三角棋盤

• Task Provider: raiso
• Task Setter: raiso

首殺 team21_24 (01:43)

解法說明

本題只想要測試各位的 dfs 能力，以及三角形棋盤的聯通性。
唯一需要注意的就是「每個 row 的邊界都不一樣大」

標準程式

#include <bits/stdc++.h>
using namespace std;

int l;
bool G[5][5] = {};

bool onBoard(int a, int b) {
  if(a < l && a >= 0 && b <= a && b >= 0) return 1;
  return 0;
}

bool dfs(int n) {
  if(n == 1) return 1;
  for(int r = 0; r < l; r++) for(int c = 0; c <= r; c++) if(G[r][c]) {
    for(int dr = -1; dr <= 1; dr++) for(int dc = -1; dc <= 1; dc++) if(dr+dc != 0) {
      int r1 = r+dr, c1 = c+dc;
      int r2 = r+dr*2, c2 = c+dc*2;
      if(onBoard(r2, c2) && G[r1][c1] && !G[r2][c2]) {
        G[r2][c2] = 1, G[r1][c1] = 0, G[r][c] = 0;
        if(dfs(n-1)) return 1;
        G[r2][c2] = 0, G[r1][c1] = 1, G[r][c] = 1;
      }
    }
  }
  return 0;
}

int main() {
  int n;
  cin >> n >> l;
  for(int i = 0; i < n; i++) {
    int a, b; cin >> a >> b, a--, b--;
    G[a][b] = 1;
  }
  bool ans = dfs(n);
  cout << (ans? "Yes": "No") << endl;
  return 0;
}

高速公路維修站

• Task Provider: baluteshih
• Task Setter: leo

首殺 team21_12 (01:49)

解法說明

本題賽後加強測資，不影響賽中 Submission。

看到值域可以很明顯的知道從每個點做一次最短路徑是行不通的，
不如我們換個想法，一個點到最近的維修站距離，
也可以視為從所有的維修站同時出發，
看哪個維修站先走到這個點，即為該點到最近維修站的距離。
那麼我們就同時從所有維修站出發，也就是做多個起點的最短路徑，
但是做

$F$ 次最短路又太耗費時間，因此可以採用一個方法，
我們使用一個「超級起點」，
且將超級起點連到所有的維修站，距離為

$0$，
則只要做一次從超級起點出發的最短路徑，
可以直接使用 dijkstra 演算法求解。

標準程式

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <bitset>
#include <cstring>
using namespace std;

struct edge{
    int to;
    long long w;
    bool operator<(const edge &a)const{
        return w > a.w;
    }
};

vector<edge> v[100001];

priority_queue<edge> q;

bitset<100001> vis;

long long dis[100001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, f, st, ed, w, f_i;
    cin >> n >> m >> f;
    memset(dis, -1, sizeof(dis));
    for(int i = 0; i < m; i++){
        cin >> st >> ed >> w;
        v[st].push_back(edge{ed, w});
        v[ed].push_back(edge{st, w});
    }
    for(int i = 0; i < f; i++)
        cin >> f_i, q.push(edge{f_i, 0});
    while(!q.empty()){
        edge tmp = q.top();
        q.pop();
        if(vis[tmp.to])
            continue;
        vis[tmp.to] = 1;
        dis[tmp.to] = tmp.w;
        for(edge i : v[tmp.to])
            if(!vis[i.to])
                q.push(edge{i.to, tmp.w + i.w});
    }
    for(int i = 1; i <= n; i++)
        cout << dis[i] << " \n"[i == n];
}

勞贖🐭

• Task Provider: ys
• Task Setter: ys

首殺 team21_24 (01:30)

解法說明

• 設沒有捕鼠器的路為
  $0$ 權重的邊
• 而含有捕鼠器的路為
  $1$ 權重的邊

目標是要找出總權重最小的連通生成子圖

連通的生成子圖就是題目要求的地圖

首先，子圖中並沒有任何的邊，可以看做子圖有

$N$ 個連通塊

一個目標要將這

$N$ 個連通塊通通相連，使得只剩

$1$ 個連通塊

接著將

$0$ 權重的邊都放入子圖中，這樣不會增加總權重，且連通塊數量會變少
最後剩下的連通塊，只能透過

$1$ 權重的邊相連。這樣產生了總權重最小的連通圖

解法 1

實作上，枚舉所有還未被 DFS 拜訪過的點
對於每一點將它能透過

$0$ 權重路徑到達的點都納入連通塊中
這部分透過 DFS，將

$0$ 權重邊拜訪到的鄰點，一層層加入到連通塊中

當無法繼續進行 DFS，表示該連通塊已生成完畢
接著對於剩下的點進行一樣的操作。

解法 2

同解法 1，可改成使用 BFS 進行點的拜訪

標準程式

解法 1

#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;

int constexpr maxn = 5e5 + 10;

int n, m;
set<int> g[maxn], rest;

void dfs(int u) {
  vector<int> nbh(rest.size()); // neighbourhood
  auto it = set_difference(all(rest), all(g[u]), nbh.begin());
  nbh.resize(it-nbh.begin());

  for(auto v: nbh) rest.erase(v);
  for(auto v: nbh) dfs(v);
}

int main()
{
  scanf("%d%d", &n, &m);

  for(int i = 0; i < m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    g[a].insert(b);
    g[b].insert(a);
  }
  
  for(int i = 1; i <= n; i++) rest.insert(i);

  int ans = -1;
  for(int i = 1; i <= n; i++) {
    if(!rest.count(i)) continue;
      
    rest.erase(i);
    dfs(i);
    ans++;
  }
  
  printf("%d\n", ans);

  return 0;
}

解法 2

#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
 
int constexpr maxn = 5e5 + 10;
 
int n, m, a, b;
set<int> g[maxn];
 
int main() {
  scanf("%d%d", &n, &m);
  while(m--) {
    scanf("%d%d", &a, &b);
    g[a].insert(b);
    g[b].insert(a);
  }
 
  set<int> rest;
  for(int i = 1; i <= n; i++) rest.insert(i);
 
  int comp = 0; // component
  queue<int> nbh; // neighbourhood
  while(rest.size()) {
    if(nbh.empty()) {
      comp++;
      nbh.push(*rest.begin());
      rest.erase(rest.begin());
    }
 
    int u = nbh.front(); nbh.pop();
 
    vector<int> diff(rest.size());
    auto it = set_difference(all(rest), all(g[u]), diff.begin());
    diff.resize(it-diff.begin());
 
    for(int v: diff) rest.erase(v), nbh.push(v);
  }
 
  printf("%d\n", comp-1);
 
  return 0;
}