这是个毛的模拟退火

正解是状压dp或者搜索

题意:给一张图(两点间可能有多条边),求一棵生成树,使得起点$$s$$(任选起点)到各个点的花费最小,输出花费,花费$$=dis[s][v] * dep[v],dep[v]$$是从s到v经过的节点数量(需沿着已经选择的路径

因为需要乘以深度,所以prim好像并不能正确求出答案

被优先级安排了

$$!rand()\%n$$

$$!(rand()\%n)$$

上面这两种写法不一样

#include <bits/stdc++.h>
using namespace std;
#define read2(a, b) (read(a), read(b))
#define read3(a, b, c) (read(a), read(b), read(c))
inline void chmin(int &x, int y) {if (x > y) x = y;}
const int inf = 0x3f3f3f3f;

template<class T> void read(T & x) {
  register int c = getchar(), f = 1; x = 0;
  while(!isdigit(c)) {if (c == '-') f = -f; c = getchar();}
  while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
  x *= f;
}
int n, m, dis[15][15], dep[15], vis[15], tot;

struct Edge{
  int u, v;
  inline bool operator < (const Edge & rhs) const {
    return dis[u][v] * dep[u] > dis[rhs.u][rhs.v] * dep[rhs.u];//堆中元素比较
  }
  Edge(int _u, int _v) : u(_u), v(_v){}
  Edge(){}
} pass[1005];

inline int Random(int s) {
  memset(dep, 0, sizeof dep); memset(vis, 0, sizeof vis);
  priority_queue<Edge>q;
  for(int i = 1; i <= n; ++i) if (dis[s][i] < inf) q.push(Edge(s, i));//将跟起点直接相连的点push入堆
  int ans = 0; dep[s] = vis[s] = 1;//dep[s]==1的原因是计算答案时用的dis[u][v]*dis[u]
  for(int i = 1; i < n; ++i) {//n-1次拓展
    Edge x = q.top(); q.pop();
    while(!q.empty() && (vis[x.v] || rand()%(n) == 0)) {//每次以一定几率忽略堆顶元素
      if (!vis[x.v]) pass[++tot] = x;//将忽略的存起来
      x = q.top(); q.pop();
    }
    vis[x.v] = 1, dep[x.v] = dep[x.u] + 1;//更新本次拓展选择的边
    while(tot) q.push(pass[tot--]);//将忽略的再push入堆
    for(int j = 1; j <= n; ++j) {
      if (dis[x.v][j] < inf && !vis[j]) q.push(Edge(x.v, j));//下一轮拓展
    }
    ans += dis[x.u][x.v] * dep[x.u];//统计答案
  }
  return ans;
}
int u, v, w;
int main(void) {
  #ifdef LOCAL_DEBUG
  freopen("data.in", "r", stdin);
  #endif
  memset(dis, 0x3f, sizeof dis); 
  read2(n, m);
  for(int i = 1; i <= m; ++i) {
    read3(u, v, w); dis[u][v] = dis[v][u] = min(dis[u][v], w);
  }
  srand(19260817);
  int Ans = inf;
  for(int i = 1; i <= 1500; ++i) {
    for(int j = 1; j <= n; ++j) chmin(Ans, Random(j));
  }
  cout << Ans;
  return 0;
}
分类: 随机化

发表评论

电子邮件地址不会被公开。 必填项已用*标注