低效率解法在
这里。
低效率的解法是没法通过POJ的数据的。
另外一个标程中的解法十分给力，仅用时110ms（status上面还有用时16ms的）
首先来看一下这段程序：
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main()
{
int INF=99999999,N,K,d[30][30],i,j,k,x,y,z,dp[256][30],e[8],v[30],c,b;
string s,t;
while (cin >> N >> K && N) {
map<string,int> cityMap;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
d[i][j]=i==j?0:INF;
for(i=0;i<N;i++) {
cin >> s;
cityMap[s]=i;
}
if (K)
while(cin >> s >> t >> z, x=cityMap[s],
y=cityMap[t],
d[x][y]=d[y][x]=min(d[y][x],z), --K);
for(k=0;k<N;k++)
for(i=0;i<N;i++)
for(j=0;j<N;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
for(i=0;i<8;i++) {
cin >> s;
e[i]=cityMap[s];
for(j=0;j<N;j++)
dp[1<<i][j]=d[j][e[i]];
}
for(i=1;i<256;i++) {
if (!(i&(i-1)))
continue;
// step1
for(k=0;k<N;k++) {
dp[i][k]=INF;
v[k]=0;
for(j=1;j<i;j++)
if ((i|j)==i)
dp[i][k]=min(dp[i][k],dp[j][k]+dp[i-j][k]);
}
// step2
for(j=0;b=INF,j<N;j++) {
for(k=0;k<N;k++)
if (dp[i][k]<=b && !v[k])
b=dp[i][c=k];
for(k=0,v[c]=1;k<N;k++)
dp[i][c]=min(dp[i][c],dp[i][k]+d[k][c]);
}
}
// step3
for(i=0,b=INF;z=0,i<256;b=min(b,z),i++)
for(j=0;y=0,j<4;z+=!!y*dp[y][x],j++)
for(k=0;k<8;k+=2)
if ((i>>k&3)==j)
y+=3<<k,x=e[k];
cout << b << endl;
}
return 0;
}
这段程序写得很让人费解。花了半天时间我才搞明白。
实际上大体的思路是跟低效率的解法一样的。
就是在求Minimal Steiner Tree这一步，它用了一种新的动态规划的方法。
动态规划的方程为：
dp[mask][i] = { 以点i为根，包含mask中的点的最小生成树的权值 }
在得知 dp[mask - 1][1...N] 的情况下，如何推出 dp[mask][1...N] 呢？
程序中分为 step1 和 step2 两个步骤。
step1 推出：
a = min{ dp[m1][i] + dp[m2][i] } 其中 m1|m2 = mask
这个很好理解。
step2 推出：
b = min{ dp[mask][j] + d[j][i] }
程序中每次都从 dp[mask][1...N] 中选出最小的一个 dp[mask][c]
按这种顺序更新就能保证结果的正确
因此 dp[mask][i] = min(a, b)
这个动态规划法的确牛逼。
step3则是枚举4条路线的各种组合情况。求出每种组合的MST权值。
代码写得很牛逼。看了半天才看懂。如果让我写，行数至少多出2，3倍来。。
老外就是牛逼，一行代码都不浪费。