Problem

Submissions

因为这题没人用 SA 写，lz 又才学 SA 1ms，不会调参。。

#include <bits/stdc++.h>
#define int long long
using namespace std;

int ans;
const int N = 105;
const double d = 0.993;
int p[N][N], a[N], n;
int val(){
    int cnt = 0;
    for(int i = 1;i < n;i ++ ) {
        cnt += p[a[i]][a[i + 1]];
    }
    return cnt;
}
void SA()
{
    double T = 100000;
    int now = ans;
    while(T > 1e-5){
        int x = rand() % n + 1, y = rand() % n + 1;
        while(x == y) x = rand() % n + 1, y = rand() % n + 1;
        swap(a[x], a[y]);
        int cnt = val(), diff = cnt - now;
        if(diff > 0){
            now = cnt; 
            if(cnt > ans) ans = cnt;
        }
        else if(RAND_MAX * exp(-diff / T) <= rand()) swap(a[x], a[y]);
        T *= d;
    }
}
signed main()
{
    srand(time(0));
    cin >> n;
    for(int i = 1;i <= n;i ++ ) a[i] = i;
    for(int i = 1;i <= n;i ++ ){
        for(int j = 1;j <= n;j ++ ){
            cin >> p[i][j];
        }
    }
    ans = val();
    for(int i = 1;i <= 1000;i ++ ) SA();
    cout << ans << endl;
    return 0;
}