另一个小疑问
  • 板块CF76A Gift
  • 楼主Moeebius
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/5/3 21:14
  • 上次更新2023/11/5 21:54:17
查看原帖
另一个小疑问
356003
Moeebius楼主2023/5/3 21:14

这是我的代码:

// 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。请问这是为什么?

2023/5/3 21:14
加载中...