集合表示多用[0,n)表示方法
HDU - 5067
经典TSP,每个顶点恰经过一次最优
#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
typedef pair<int,int> P;
int dp[1<<12][20];
int G[56][78],r,c;
P biao[23];
inline int dis(P a,P b){
return abs(a.first-b.first)+abs(a.second-b.second);
}
int DP(int S,int v,int cnt){
if(dp[S][v]>=0) return dp[S][v];
if(S==(1<<cnt)-1&&v==0) return dp[S][v]=0;
int ans=0x3f3f3f3f;
rep(u,0,cnt-1){
if(!(S>>u&1)){
ans=min(ans,DP(S|(1<<u),u,cnt)+dis(biao[u],biao[v]));
}
}
return dp[S][v]=ans;
}
int main(){
while(scanf("%d%d",&r,&c)!=EOF){
int cnt=0;
rep(i,0,r-1)rep(j,0,c-1)scanf("%d",&G[i][j]);
rep(i,0,r-1)rep(j,0,c-1){
if(G[i][j]||(i==0&&j==0)){
biao[cnt++]=P(i,j);
}
}
memset(dp,-1,sizeof dp);
printf("%d\n",DP(0,0,cnt));
}
return 0;
}
HDU - 5418
多次遍历TSP
用floyd使它无后效性
然后同上
#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int dp[1<<18][17];
int G[18][18],n,m,u,v,w;
int DP(int S,int u,int n){
if(dp[S][u]>=0) return dp[S][u];
if(S==(1<<n)-1&&u==0) return dp[S][u]=0;
int ans=0x3f3f3f3f;
rep(v,0,n-1){
if(!(S>>v&1)){
ans=min(ans,DP(S|(1<<v),v,n)+G[u][v]);
}
}
return dp[S][u]=ans;
}
int main(){
int T; scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
memset(G,0x3f,sizeof G);
memset(dp,-1,sizeof dp);
rep(i,1,m){
scanf("%d%d%d",&u,&v,&w);
u--; v--;
G[u][v]=min(G[u][v],w);
G[v][u]=min(G[v][u],w);
}
rep(i,0,n-1) G[i][i]=0;
rep(i,0,n-1) rep(j,0,n-1)if(i!=j){
rep(k,0,n-1)
G[i][j]=min(G[i][j],G[i][k]+G[k][j]);
}
printf("%d\n",DP(0,0,n));
}
return 0;
}