请问有没有大佬知道下面代码为什么使用连接一次边连通块数量减1就只能通过70分。
重新写个循环就可以AC。在印象中是可以这样判断有没有最小生成树把,而且同样的最小生成树H题这样写法都可以通过。
#include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define all(__vv__) (__vv__).begin(), (__vv__).end() #define endl "\n" #define pai pair<int, int> #define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__)) #define rep(i, sta, en) for(int i=sta; i<=en; ++i) typedef long long ll; typedef unsigned long long ull; typedef long double ld; inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; } inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); } inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; } ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; } const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} }; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; const int N = 2e5 + 7; const int M = 2e6 + 7; ll n, m; int head[N], tot, fa[N]; map<string, int> mp; struct Node { string u, v; ll w; bool operator < (const Node& opt) const { return w < opt.w; } }edge[M]; int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } void solve() { mp.clear(); rep(i, 1, N - 1) fa[i] = i; string st; cin >> st; int cnt = 0; rep(i, 1, m) { cin >> edge[i].u >> edge[i].v; cin >> edge[i].w; if (!mp.count(edge[i].u)) mp[edge[i].u] = ++cnt; if (!mp.count(edge[i].v)) mp[edge[i].v] = ++cnt; } sort(edge + 1, edge + 1 + m); cnt = n; ll ans = 0; rep(i, 1, m) { int fu = find(mp[edge[i].u]), fv = find(mp[edge[i].v]); if (fu != fv) { fa[fv] = fu; ans += edge[i].w; --cnt; } if (cnt == 1) break; } // if (cnt == 1) cout << ans << endl; wa的 // else cout << "NO!" << endl; int flag = 1; // ac的 int flag1 = 1; rep(i, 1, n) { if (fa[i] == i && !flag) { flag1 = 0; } if (fa[i] == i && flag) { flag = 0; } } if (flag1) cout << ans << endl; else cout << "No!" << endl; } int main() { js; //int T = read(); while (cin >> n >> m) solve(); return 0; }
全部评论
(1) 回帖