QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#758155 | #8136. Rebellious Edge | dadas | RE | 0ms | 0kb | C++17 | 2.3kb | 2024-11-17 16:14:16 | 2024-11-17 16:14:16 |
answer
#include <bits/stdc++.h>
using namespace std;
#define ing long long
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
//#pragma GCC optimize("O3,unroll-loops")
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define F first
#define S second
#define SZ(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
#define cl clear
#define endl '\n'
#define deb(x) cerr << #x << " = " << x << '\n'
#define dokme(x) {cout << x << endl; return;}
#define wtf cout << "[ahaaaaaaaaaaaaaaaa]" << endl;
const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const int inf = 1e9 + 90;
const int maxLG = 20;
const int SQ = 350;
ll n, m, dist[MAXN];
set<pll> G[MAXN];
bool mark[MAXN];
set<pii> se;
ll MST = 0;
void add(ll v) {
for (auto [u, w] : G[v]) {
if (!mark[u]) {
se.erase({dist[u], u});
se.insert({(dist[u] = w), u});
}
}
}
void prim() {
dist[1] = 0;
add(1);
se.insert({0, 1});
for (ll i = 1; i <= n; i++) {
if (se.empty()) {
return;
}
auto tmp = *(se.begin());
ll v = tmp.S;
MST += tmp.F;
se.erase(tmp);
add(v);
mark[v] = 1;
}
}
void reset() {
memset(dist, 63, sizeof dist);
for (ll i = 1; i <= n; i++)
G[i].cl();
memset(dist, 63, sizeof dist);
se.cl();
memset(mark, false, sizeof mark);
MST = 0;
}
signed main() {
migmig;
ll T;
cin >> T;
while (T--) {
cin >> n >> m;
reset();
ll b, tmp;
vector<pair<pii, ll>> edg;
for (ll i = 1; i <= m; i++) {
ll v, u, w;
cin >> v >> u >> w;
if (v > u) {
b = u;
tmp = w;
}
G[v].insert({u, w});
edg.pb({{v, u}, w});
}
G[b].cl();
for (ll i = 1; i <= n; i++) {
for (auto [x, w] : G[i]){
if (x == b) {
G[i].erase({x, w});
}
}
}
prim();
// deb(tmp);
ll res1 = MST + tmp;
MST = 0;
reset();
ll c;
for (auto x : edg) {
ll v = x.F.F, u = x.F.S, w = x.S;
if (v < u)
G[v].insert({u, w});
else
c = v;
}
G[c].cl();
prim();
ll res2 = MST;
cout << min(res1, res2) << endl;
reset();
// deb(res1 << ' ' << res2);
}
return 0;
}
/*
5 6
1 2 4
1 3 2
2 3 0
3 4 1
4 5 1
5 2 1
*/
详细
Test #1:
score: 0
Runtime Error
input:
3 5 6 1 2 4 1 3 2 2 3 0 3 4 1 4 5 1 5 2 1 4 4 1 2 4 1 3 6 1 4 8 4 2 1000000 3 3 1 2 100 2 1 10 2 3 1000