元豪 发表于 2023-5-3 15:23:50

蒟蒻再次求助！！

O2优化 , 常数优化都弄了，还是过不了{:10_266:}

哪位dalao帮忙优化一下效率啊{:10_250:}

/* https://www.luogu.com.cn/problem/P1536 -- 村村通 */

/**/

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

map <int, int> g;
int n, m, a, b, c, d;

int find(int a){
    if (g == a){
      return a;
    }
    else{
      return find(g);
    }
}

int main(){
    freopen("Input.in", "r", stdin);
    while (true){
      int ans = 0;
      scanf("%d", &a);
      if (a == 0) break;
      for (int i = 0; i < a; i++) g = i + 1;
      scanf("%d", &b);
      for (int i = 0; i < b; i++){
            scanf("%d%d", &c, &d);
            g = find(d);
      }
      for (int i = 0; i < a; i++){
            if (find(i + 1) == i + 1){
                ans++;
            }
      }
      printf("%d\n", ans - 1);
    }

    return 0;
}

元豪 发表于 2023-5-3 15:24:13

代码里有题目链接{:10_266:}{:10_266:}

元豪 发表于 2023-5-3 15:24:32

@isdkz

陶远航 发表于 2023-5-3 15:24:50

这段代码中使用了递归的方式进行 find 操作，可能会导致栈空间过度消耗。建议使用循环代替递归。

另外，map 会增加常数开销，建议考虑使用数组代替 map 存储并查集。

下面是优化后的代码示例，希望对您有所帮助：
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int fa;

int find(int x) {
    if (fa == x) return x;
    return fa = find(fa);
}

int main() {
    int n, m, a, b, c, d;
    while (true) {
      scanf("%d", &n);
      if (n == 0) break;
      for (int i = 1; i <= n; i++) fa = i;
      scanf("%d", &m);
      for (int i = 0; i < m; i++) {
            scanf("%d%d", &a, &b);
            fa = find(b);
      }
      int ans = 0;
      for (int i = 1; i <= n; i++) {
            if (fa == i) ans++;
      }
      printf("%d\n", ans - 1);
    }
    return 0;
}

元豪 发表于 2023-5-3 15:26:28

陶远航 发表于 2023-5-3 15:24
这段代码中使用了递归的方式进行 find 操作，可能会导致栈空间过度消耗。建议使用循环代替递归。

另外， ...

哦，原来是map有问题{:10_257:}

感谢大佬{:5_106:}

歌者文明清理员 发表于 2023-5-3 15:30:56

元豪 发表于 2023-5-3 15:26
哦，原来是map有问题

感谢大佬

下面是完整的 C++ 代码实现，主要使用了 Kruskal 算法。

时间复杂度为 O(mlogm)，其中 m 是边数。
下面是完整的 C++ 代码实现：

cpp
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 100010;
const int MAXM = 200010;

int n, m;
int p, rank;

struct Edge {
    int u, v, w;
} e;

bool cmp(const Edge& a, const Edge& b) {
    return a.w < b.w;
}

int find(int x) {
    if (x != p) p = find(p);
    return p;
}

void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (rank < rank) swap(x, y);
    p = x;
    if (rank == rank) ++rank;
}

int kruskal() {
    sort(e, e + m, cmp);
    for (int i = 1; i <= n; ++i) {
      p = i;
      rank = 0;
    }
    int res = 0, cnt = 0;
    for (int i = 0; i < m; ++i) {
      if (cnt == n - 1) break;
      int u = e.u, v = e.v, w = e.w;
      if (find(u) == find(v)) continue;
      unite(u, v);
      res += w;
      ++cnt;
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
      int u, v, w;
      scanf("%d%d%d", &u, &v, &w);
      e = {u, v, w};
    }
    printf("%d\n", kruskal());
    return 0;
}

isdkz 发表于 2023-5-3 15:33:59

元豪 发表于 2023-5-3 15:24
@isdkz

来晚了{:10_250:}

元豪 发表于 2023-5-3 15:39:19

isdkz 发表于 2023-5-3 15:33
来晚了

{:5_109:}

sfqxx 发表于 2023-5-3 15:57:00

妈呀，陶远航

元豪 发表于 2023-5-3 16:08:44

sfqxx 发表于 2023-5-3 15:57
妈呀，陶远航

他在我发表1分钟后就回复了{:10_256:}
页: [1]
查看完整版本: 蒟蒻再次求助！！