这题是个有向图,看似要跑最小树形图,但是一般的朱刘算法 $O(nm)$ 跑不完,$O((n+m)\log n)$ 的最小树形图在这里用处也不大,因为要先求能到达多少个节点。不难发现我们可以转一般的无向图来做。
首先我们根据题目要求添加有向边,高处指向低处。需要注意,相同高度可以互相到达。
接下来做 bfs
,只要这条边可以抵达就加入真正的边集,当做无向边来计算。
最后做 kruskal
,最先对边集排序,考虑带加边的过程不能单纯按一般最小生成树那样去加,我们可以模拟从山上滑下来的过程,优先加边的流向高度更高的边,然后第二优先加边权小的就可以了。
int n, m;
int reach_pt;
i64 min_route;
// standard edge
struct edge
{
int to, nxt, w;
} e[M << 1];
int he[N], cnt;
int H[N];
void add_edge(int u, int v, int w)
{
e[++cnt].to = v, e[cnt].nxt = he[u];
e[cnt].w = w, he[u] = cnt;
}
int real_cnt;
struct real_edge
{
int u, v, w;
bool operator<(const real_edge& o) const
{
if (H[v] ^ H[o.v])
return H[v] > H[o.v];
else
return w < o.w;
}
} r[M << 1];
// bfs
std::queue<int> q;
bool vis[N];
void bfs(int rt)
{
q.push(rt), vis[rt] = 1, ++reach_pt;
while (q.size())
{
int u = q.front();
q.pop();
for (int i = he[u]; i; i = e[i].nxt)
{
r[real_cnt++] = {u, e[i].to, e[i].w};
if (!vis[e[i].to])
vis[e[i].to] = 1, ++reach_pt, q.push(e[i].to);
}
}
}
// union find
int f[N], sz[N];
void init_f()
{
for (int i = 1; i <= n; ++i)
f[i] = i, sz[i] = 1;
}
int getf(int x) { return f[x] == x ? x : f[x] = getf(f[x]); }
bool check(int x, int y)
{
int fx = getf(x), fy = getf(y);
return (fx ^ fy) ? 1 : 0;
}
void merg(int x, int y)
{
int fx = getf(x), fy = getf(y);
if (fx ^ fy)
{
if (sz[fx] > sz[fy])
f[fy] = fx, sz[fx] += sz[fy], sz[fy] = 0;
else
f[fx] = fy, sz[fy] += sz[fx], sz[fx] = 0;
}
}
void kruskal()
{
std::sort(r, r + real_cnt);
init_f();
for (int i = 0; i < real_cnt; ++i)
if (check(r[i].u, r[i].v))
merg(r[i].u, r[i].v), min_route += r[i].w;
}
int main()
{
n = rd(), m = rd();
for (int i = 1; i <= n; ++i)
H[i] = rd();
while (m--)
{
int u = rd(), v = rd(), w = rd();
if (H[u] >= H[v])
add_edge(u, v, w);
if (H[v] >= H[u])
add_edge(v, u, w);
}
bfs(1);
kruskal();
wr(reach_pt), putchar(' '), wr(min_route);
}