20250427 TTC 題解

pA

author : paul
problem setter : blame

First Killed : ®Blameazu®┻━┻ ︵ヽ(`Д´)ﾉ︵ ┻━┻

給定一個

$N$ 點

$M$ 邊的無向圖，問跟點

$1$ 距離

$>6$ 的有幾個點(每一條邊的距離為

$1$)
無連通視為距離

$\mathrm{\infty }$

子任務2

鍊狀圖

隨便dfs即可

滿分解

放輕鬆，BFS即可

vector<int> dis(n+1, -1);
dis[1] = 0;
queue<int> qq({1});
while(qq.size()) {
    int now = qq.front();
    qq.pop();
    for(auto &d : g[now]) if(dis[d] == -1) {
        dis[d] = dis[now] + 1;
        qq.push(d);
    }
}
cout << count_if(dis.begin()+1, dis.end(), [&](int x) 
                 {return x > 6 || x == -1;}) << '\n';

pB

author : blame
problem setter : blame

First Killed : ®Blameazu®┻━┻ ︵ヽ(`Д´)ﾉ︵ ┻━┻

給一張

$N$ 點

$M$ 邊的有向圖
求有多少點在環上，或者可以從某個環上走到。

子任務二

大概是dfs隨便做一做都有

滿分解

拓樸排序後剩下來沒 visited 過的點即為答案
拓樸排序可以採用Kahn's Algorithm

bonus

有人硬砸 SCC 把他砸過去了 ==

pC

author : charhao
problem setter : charhao

First Killed : KCC

給

$n$ 點

$m$ 邊的無向連通圖，每條邊上都有一個邊權

$w_i$

定義一條

$a$ 到

$b$ 的"最佳路徑"為

$a$ 到

$b$ 所有路徑中最大邊權最小的那一條路徑

定義

$a$ 到

$b$ 的距離為

$a$ 到

$b$ 的最佳路徑上最大的邊權

求第

$K$ 小的距離為多少

滿分解

先從小到大排序邊權，然後用DSU維護第

$i$ 條邊可以讓多少點對的答案是

$w_i$，重複直到合起來的總點對數量超過

$K$

pD

source : https://www.luogu.com.cn/problem/P5905
problem setter : blame

First Killed :

給定一張

$N$ 點

$M$ 邊的帶權有向圖

問所有點之間的最短路

假如圖中有負環，請直接輸出 "-1"

子任務 2

手動判斷

子任務 3

暴力解，可以採用 floyd-warshall

子任務 4

做

$N$ 次 Dijkstra

滿分解

這題是 Johnson 全點對最短路的裸題
先對圖做一次 Bellman Ford 判斷負環
(這邊要開一個虛擬點

$0$ 對所有的點加邊權為

$0$ 的邊)
再做

$N$ 次Dijkstra，
但因為 Dijkstra 在負權圖上會吃WA or 吃TLE
所以要用勢能分析的方式解決 (詳細證明網路上找都有)

複雜度

$O(NM+N(N+M)log(M))$

bonus

這題嚴格比對

Conclusion and Some Complaints

除了 charhao 出的 pC 外
其他題目皆有分子任務出來
撈子任務其實是一個技巧
希望下次可以看到各位更努力的撈分
這樣才能使競爭更加激烈且健康 :)