当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 洛谷P3959 宝藏(模拟退火乱搞)

洛谷P3959 宝藏(模拟退火乱搞)

2018年09月13日  | 移动技术网IT编程  | 我要评论

日本旅游签证时间,sd5000,黄家驹北京演唱会

题意

题目链接

题面好长啊。。。自己看吧。。

sol

自己想了一个退火的思路，没想到第一次交85，多退了几次就a了哈哈哈

首先把没用的边去掉，然后剩下的边从小到大排序

这样我们就得到了一个选边的序列，我们要求答案强制按照这个序列选

每次退火的时候选两个点交换。

枚举每个点，判断是否能更新答案，

时间复杂度$o(200 * 1000 * n * m)$

/*
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<algorithm>
#include<vector>
#define pair pair<int, int> 
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
const int maxn = 1001;
const double eps = 1e-10, dlt = 0.97, inf = 1e9 + 7;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m;
struct edge {
    int u, v, w;
    bool operator < (const edge &rhs) const {
        return w < rhs.w;
    }
}e[maxn];
int link[maxn][maxn], num, fa[maxn];
void unionn(int x, int y) {
    fa[x] = y;
}
int find(int x) {
    if(fa[x] == x) return fa[x];
    else return fa[x] = find(fa[x]);
}
vector<pair> v[maxn];
int dfs(int x, int cnt, int fa) {
    int ans = 0;
    for(int i = 0; i < v[x].size(); i++) {
        int to = v[x][i].fi, w = v[x][i].se;
        if(to != fa) ans += dfs(to, cnt + 1, x) + w * cnt;
    }
    return ans;
}
int solve() {
    int cur = inf, tot = 0, base = 0;
    for(int i = 1; i <= n; i++) fa[i] = i, v[i].clear();
    for(int i = 1; i <= m; i++) {
        int x = e[i].u, y = e[i].v;
        int fx = find(x), fy = find(y);
        if(fx == fy) continue;
        tot++; unionn(fx, fy); 
        v[x].push_back(mp(y, e[i].w));
        v[y].push_back(mp(x, e[i].w));
    }
    if(tot != n - 1) return inf;
    for(int i = 1; i <= n; i++)
        cur = min(cur, dfs(i, 1, 0));
    return cur;
}
int main() {
//    freopen("testdata.in", "r", stdin);
    srand((unsigned)time(null));
    memset(link, 0x7f, sizeof(link));
    n = read(); m = read();
    if(n == 1) {
        puts("0"); return 0;
    }
    for(int i = 1; i <= m; i++) {
        int x = read(), y = read(), w = read();
        link[x][y] = min(link[x][y], w);
        link[y][x] = min(link[y][x], w);
    }
    for(int i = 1; i <= n; i++) 
        for(int j = i + 1; j <= n; j++) 
            if(link[i][j] <= inf) 
                e[++num] = (edge) {i, j, link[i][j]};
    sort(e + 1, e + num + 1);
    int ans = solve();
    int times = 200;
    while(times--) {
        int now = inf;
        for(double t = 100000; t > eps; t *= dlt) {
            int x = rand() % num + 1, y = rand() % num + 1;
            //check(x, y);
            swap(e[x], e[y]);
            int nxt = solve();
            if(nxt < ans) {ans = nxt; continue;}
            if(nxt < now || ((exp(now - nxt / t) < rand() / rand_max))) {now = nxt; continue;}
            swap(e[x], e[y]);
        }
    }
    printf("%d", ans);
    return 0;
}
/*
4
0 0
0 5000
2354 10000
8787 0
*/

 

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网