C++(clang++ 11.0.1) 解法, 执行用时: 1411ms, 内存消耗: 540K, 提交时间: 2023-06-28 08:33:22

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
const ui N(41);
ui e[N][N], g[N][N];
ui n, a, b, lim, val, lef, ans;
ui cond[N], cono[N], *d(cond), *ord(cono);
inline bool cmp(const ui a, const ui b) { return d[a] < d[b]; }
void dfs(void) {
  // putc('1', stderr);
  if (!lef) {
    if (val < ans)
      ans = val;
    return;
  }
  // putc('2', stderr);
  ui sum(0);
  for (ui i(0); i < lef; i++)
    sum += d[ord[i]];
  if (val + b * lef >= ans + sum * a)
    return;
  // putc('3', stderr);
  ui pcond[N], pcono[N], *pd(d), *pord(ord), pval(val), u, v;
  d = pcond, ord = pcono;
  for (ui pl(lef); pl--;) {
    u = pord[pl];
    val = pval - pd[u] * a + b, lef = 0;
    for (ui j(0); j < pl; j++) {
      v = pord[j];
      if (pd[v] > lim + e[u][v])
        d[ord[lef++] = v] = pd[v] - e[u][v];
    }
    sort(ord, ord + lef, cmp);
    dfs();
  }
  val = pval, d = pd, ord = pord;
}
int main(void) {
  ui t;
  scanf("%u", &t);
  while (t--) {
    ui m;
    scanf("%u%u%u%u", &n, &m, &a, &b);
    lim = (b - 1) / a, ans = val = m * a, lef = 0;
    memset(e, 0, sizeof e), memset(cond, 0, sizeof cond);
    while (m--) {
      ui u, v;
      scanf("%u%u", &u, &v);
      if (u == v)
        e[u][u]++, d[u]++;
      else
        e[u][v]++, e[v][u]++, d[u]++, d[v]++;
    }
    for (ui i(1); i <= n; i++)
      if (d[i] > lim)
        ord[lef++] = i;
    sort(ord, ord + lef, cmp);
    dfs();
    printf("%u\n", ans);
  }
  return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 1497ms, 内存消耗: 23936K, 提交时间: 2023-06-27 12:36:42

#include <bits/stdc++.h>
#define int long long
#define pb push_back 
using namespace std;
mt19937 rnd(chrono::system_clock().now().time_since_epoch().count());
int gen(int l,int r) {return rnd()%(r-l+1)+l;}
const int INF=1e6+5;
int n,m,p[INF],ans,vis[INF],a,b;
vector <int> e[INF];
int check() {
    int ans=1e18,cnt=m,cnt1=0;
    for (int i=1;i<=n;i++) vis[i]=0;
    for (int i=1;i<=n;i++) {
        int d=0;
        for (int v:e[p[i]])
            if (!vis[v] || v==p[i]) d++;
        if (d*a<b) ;
        else cnt1++,cnt-=d,vis[p[i]]=1;;
        ans=min(ans,cnt1*b+cnt*a);
    }
    return ans;
}
void SA() {
    int res=1e18;
    double T=2008;
    while (T>=1e-12) {
        int x=gen(1,n),y=gen(1,n);
        swap(p[x],p[y]);
        int now=check();
        if (now<res) res=now;
        else if (exp(-(res-now)/T*RAND_MAX)>rand()) swap(p[x],p[y]);
        T*=0.997;
    }
    ans=min(res,ans);
}
void solve() {
    // double st=clock();
    cin>>n>>m>>a>>b;ans=min(n*b,m*a);
    for (int i=0;i<=n+2;i++) vector <int> ().swap(e[i]);
    for (int i=1;i<=m;i++) {
        int x=0,y=0;
        cin>>x>>y;
        e[x].pb(y);
        if (x!=y) e[y].pb(x);
    }
    int TT=30;
    for (int i=1;i<=n;i++) p[i]=i;
    while (TT--) SA();
    cout<<ans<<"\n";
    return ;
}
signed main()
{
    srand(114514);
    ios::sync_with_stdio(false);
    int t=0;cin>>t;
    while (t--) solve();
    return 0;
}