期中考終于考完了，整道題獎勵下自己

我一北大同學問我的，說他遞歸超時了，叫我想一個辦法

后面他說他加了個剪枝就過了，然后我自己嘗試了一個方法：

就是先把城市按1到n排列，然后考慮互換，如果互換后更便宜就換

這樣下去的排列一直最優化進行

最后不能最優的時候就ok了

代碼如下：

#include<stdio.h>
int cost[16][16];
int r[16];//routeint main(void)
{int n, m = 0, count = 1;scanf("%d", &n);for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++)scanf("%d", &cost[i][j]);r[i] = i;}//先計算總價錢mfor(int i = 1; i < n; i++)m += cost[i][i + 1];m += cost[1][n];//開始找最優解while(count){count = 0;for(int b = 1; b < n; b++){int a = (b == 1) ? n : b - 1;int c = b + 1;for(int e = b + 1; e <= n; e++){int d = e - 1;int f = (e == n) ? 1 : e + 1;int former = cost[r[a]][r[b]] + cost[r[b]][r[c]] + cost[r[d]][r[e]] + cost[r[e]][r[f]];r[b] ^= r[e] ^= r[b] ^= r[e];int later = cost[r[a]][r[b]] + cost[r[b]][r[c]] + cost[r[d]][r[e]] + cost[r[e]][r[f]];if(former > later){m -= former - later;count++;}elser[b] ^= r[e] ^= r[b] ^= r[e];}}}printf("%d", m);return 0;
}

想象很美好，結果呢？

沒過

因為如果互換后價格一樣，你是換還是不換？

考慮換的話可能最后不是最優，不換的話最后也可能不是最優

所以兩個都要試一下

這樣就不如遞歸剪枝

（注：a ^= b ^= a ^= b; 可以使二者互換，但是使用場景較少）

代碼如下：

#include<stdio.h>
void dg(int x, int c);
int cost[16][16], city[16], r[16];//city route
int n, m;int main(void)
{scanf("%d", &n);for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)scanf("%d", &cost[i][j]);//先計算總價錢mfor(int i = 1; i < n; i++)m += cost[i][i + 1];m += cost[1][n];dg(1, 0);printf("%d", m);return 0;
}
void dg(int x, int c)//c為cost
{for(int i = 1; i <= n; i++)if(!(city[i])){if(x == 1){city[i] = 1, r[x] = i;dg(x + 1, 0);city[i] = 0, r[x] = 0;}else if(x == n){c += cost[i][r[x - 1]] + cost[i][r[1]];m = (c > m) ? m : c;c -= cost[i][r[x - 1]] + cost[i][r[1]];}else{c += cost[i][r[x - 1]];if(c <= m){city[i] = 1, r[x] = i;dg(x + 1, c);city[i] = 0; r[x] = 0;}c -= cost[i][r[x - 1]];}}return;
}

后面還是超時

不知道為什么，思路和我同學都一樣

代碼如下：

#include<iostream>
using namespace std;
int n;
int a[15][15];
int b[15]{};
int i, j, k;
int c = 0;
int cost(int c1,int i) {if(c1>=c){return 0;}int j;int flag = 0;for (j = 0; j < n; j++) {if (b[j] == 0) {flag = 1;b[j] = 1;cost(c1 + a[i][j], j);b[j] = 0;}}if (flag == 0) {c1 += a[i][0];if (c1 < c) {c = c1;}}return 0;
}
int main() {cin >> n;for (i = 0; i < n; i++) {for (j = 0; j < n; j++) {cin >> a[i][j];}}for (i = 0; i < n; i++) {if (i < n - 1) {c += a[i][i + 1];}else {c += a[i][0];}}b[0]=1;cost(0,0);cout << c << endl;return 0;
}

（引自北京大學2023級最強新生）