提供另一个建模的思路.-. 虽然到头来没有打。

Problem

https://www.luogu.org/problemnew/show/P1268

Solution

在矩阵图上随机选择起点跑 TSP，除二就是答案。

证明挺简单的，自己想吧.-.

然后就可以模拟退火 / 粒子群什么的乱搞了

很难打

最后还是选择构造去了...

Code

// Code by ajcxsu
// Problem: weight

#include<bits/stdc++.h>
using namespace std;
int e[40][40];

int main() {
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n, n) {
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++) cin>>e[i][j], e[j][i]=e[i][j];
        int ans=e[1][2], len;
        for(int i=3;i<=n;i++) {
            len=0x3f3f3f3f;
            for(int j=1;j<i;j++)
                for(int k=j+1;k<i;k++)
                    len=min(len, e[i][j]+e[i][k]-e[j][k]>>1);
            ans+=len;
        }
        cout<<ans<<endl;
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-1268.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆