Codeforces 1108F（克鲁斯卡尔的理解）

最小生成树会多样的情况是：两个或多个边等长且连通同样的两个并查集块。

所以可以跑一遍克鲁斯卡尔，每次把当前等长的边数出来，注意不要边找边并查，因为有一部分边是正常跑生成树我们也不会要他的，这种直接跳了；还有一些，是因为你选择了第一个边，然后并在一起了，这时扫到后面的边时他自然会被抛弃。而这种比较委屈的、因为先来后到而被抛弃的边的个数，正是本题答案。如果贪心地并查地话，无法区分这个是本来就跳的，还是我们要找的。

 const int maxn = 2e5 + ;

 int n, m, f[maxn], ans;

 struct Edge {

     int u, v, cost;

     bool operator < (const Edge& rhs) const {

         return cost < rhs.cost;

     }

 }e[maxn];

 inline int getf(int v) { return v == f[v] ? v : f[v] = getf(f[v]); }

 int main() {

     read(n), read(m);

     rep(i, , n)    f[i] = i;

     rep(i, , m) {

         read(e[i].u);

         read(e[i].v);

         read(e[i].cost);

     }

     sort(e + , e +  + m);

     for (int i = , j; i <= m; i = j) {

         for (j = i; j <= m && e[j].cost == e[i].cost; j++);

         int cnt = ;

         rep(k, i, j - ) {

             if (getf(e[k].u) != getf(e[k].v))

                 cnt++;

         }

         rep(k, i, j - ) {

             if (getf(e[k].u) != getf(e[k].v)) {

                 f[getf(e[k].u)] = getf(e[k].v);

                 cnt--;

             }

         }

         ans += cnt;

     }

     writeln(ans);

     return ;

 }

巴特西

Codeforces 1108F（克鲁斯卡尔的理解）

最新文章

热门文章