低效率解法在
這里。
低效率的解法是沒法通過POJ的數(shù)據(jù)的。
另外一個標程中的解法十分給力，僅用時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;
}
這段程序?qū)懙煤茏屓速M解。花了半天時間我才搞明白。
實際上大體的思路是跟低效率的解法一樣的。
就是在求Minimal Steiner Tree這一步，它用了一種新的動態(tài)規(guī)劃的方法。
動態(tài)規(guī)劃的方程為：
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]
按這種順序更新就能保證結(jié)果的正確
因此 dp[mask][i] = min(a, b)
這個動態(tài)規(guī)劃法的確牛逼。
step3則是枚舉4條路線的各種組合情況。求出每種組合的MST權值。
代碼寫得很牛逼。看了半天才看懂。如果讓我寫，行數(shù)至少多出2，3倍來。。
老外就是牛逼，一行代碼都不浪費。