这是我的代码:
// clang-format off
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define mkp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define lll __int128
#define ll long long
#define For(i,j,k) for(int i=(j); i<=(k); ++i)
#define ForDown(i,j,k) for(int i=(j); i>=(k); --i)
#define pb push_back
#define FileIO(filename) freopen(filename ".in" ,"r",stdin);freopen(filename ".out" ,"w",stdout)
template<typename T>
il void read(T &x){ x=0;int f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}x*=f;}
template<typename T, typename ... Args>
il void read(T &x, Args &... y){ read(x);read(y...); }
// File head end
// clang-format on
const int MAXN = 205, MAXM = 5e4 + 5;
int n, m, f[MAXN];
ll ans = LLONG_MAX, G, S;
struct Edge {
int u, v;
ll g, s;
bool operator<(const Edge &rhs) const { return s < rhs.s; }
} E[MAXM];
vector<Edge> del;
multiset<Edge> ed;
int find(int x) { return f[x] == x ? f[x] : f[x] = find(f[x]); }
il void calc(int id) {
ll maxS = 0;
int cnt = 0;
for (Edge x : ed) {
int u = find(x.u), v = find(x.v);
if (u == v)
del.pb(x);
else {
maxS = max(maxS, x.s);
cnt++, f[u] = v;
}
}
if (del.size() > 5 * n) // 如果注释掉这一行乱搞,就会 WA on #4
for (Edge x : del)
ed.erase(ed.lower_bound(x));
if (cnt < n - 1)
return;
ans = min(ans, G * E[id].g + S * maxS);
}
signed main() {
read(n, m, G, S);
For(i, 1, m) { read(E[i].u, E[i].v, E[i].g, E[i].s); }
sort(E + 1, E + 1 + m,
[&](const Edge &a, const Edge &b) { return a.g < b.g; });
For(i, 1, m) {
iota(f + 1, f + 1 + n, 1), del.clear();
ed.insert(E[i]);
if ((signed)ed.size() < n - 1)
continue;
calc(i);
}
if (ans == LLONG_MAX)
puts("-1");
else
cout << ans << endl;
return 0;
}
由于一些奇妙的原因,我设置「只有当可以删除的边数大于阈值时,才执行删除」可以 AC,但如果直接删边就会 WA。请问这是为什么?