若$k\leq 15$，那么可以设$d[i][S]$表示经过了$S$集合的边，现在位于$i$点的最短路。
可以用Dijkstra算法在$O(n^22^k)$时间内求出。
否则若$k>15$，那么最坏情况下，它们会形成一个团，将这$k$条边连上后，图中最多剩下$7$个连通块。
如果知道哪些边要走，哪些边不走的话，那么只要存在欧拉回路就可以。
也就是说，所有点的度数都是偶数，且从$1$出发可以到达$k$条边的端点。
于是考虑DP，设$f[i][j][k]$表示考虑前$i$条边，目前连通性为$j$，每个点度数的奇偶性为$k$的最小代价。
时间复杂度$O(n^2Bell(7)2^n)$，状态比较稀疏，可以通过。
#include<cstdio>#include<queue>#include<vector>#include<algorithm>#include<map>using namespace std;typedef pair<int,int>P;typedef pair<int,P>PI;typedef long long ll;const int N=13,M=880,inf=100000000,LIM=15;int n,m,K,o,i,j,k,x,y,z;inline void up(int&a,int b){a>b?(a=b):0;}namespace SMALL{int f[N][N][2],g[N][N],d[N][1<<LIM];priority_queue<PI,vector<PI>,greater<PI> >q;inline void ext(int x,int y,int z){ ?if(d[x][y]<=z)return; ?q.push(PI(d[x][y]=z,P(x,y)));}void solve(){ ?for(i=0;i<n;i++)for(j=0;j<n;j++)f[i][j][0]=-1; ?for(i=0;i<n;i++)for(j=0;j<n;j++)g[i][j]=inf; ?for(i=0;i<K;i++){ ???scanf("%d%d%d",&x,&y,&z);x--,y--; ???f[x][y][0]=f[y][x][0]=i; ???f[x][y][1]=f[y][x][1]=z; ?} ?scanf("%d",&m); ?while(m--){ ???scanf("%d%d%d",&x,&y,&z);x--,y--; ???up(g[x][y],z),up(g[y][x],z); ?} ?for(i=0;i<n;i++)for(j=0;j<1<<K;j++)d[i][j]=inf; ?ext(0,0,0); ?while(!q.empty()){ ???PI t=q.top();q.pop(); ???x=t.second.first,y=t.second.second,z=t.first; ???if(z>d[x][y])continue; ???for(i=0;i<n;i++){ ?????if(~f[x][i][0])ext(i,y|(1<<f[x][i][0]),z+f[x][i][1]); ?????ext(i,y,z+g[x][i]); ???} ?} ?printf("%d",d[0][(1<<K)-1]);}}namespace BIG{bool must[N];int a[N],h,t,e[N][N],dp[2][1<<N],g[M][N][N],ans=inf;int w[2][M][1<<N];char T,v[2][M][1<<N];short s[2][M][1<<N],cnt[2][M];ll q[M];map<ll,int>id;inline void merge(int x,int y){ ?x=a[x],y=a[y]; ?for(int i=0;i<n;i++)if(a[i]==x)a[i]=y;}inline ll encode(){ ?int i,m=0;ll t=0; ?static int v[N]; ?for(i=0;i<n;i++)v[a[i]]=-1; ?for(i=0;i<n;i++){ ???if(v[a[i]]<0)v[a[i]]=m++; ???t=t<<4|v[a[i]]; ?} ?return t;}inline void decode(ll f){for(int i=n-1;~i;i--)a[i]=f&15,f>>=4;}inline bool check(ll f){ ?decode(f); ?for(int i=0;i<n;i++)if(must[i]&&a[i]!=a[0])return 0; ?return 1;}inline int ext(ll x){ ?int&o=id[x]; ?if(o)return o; ?q[o=++t]=x; ?return o;}inline void clr(){ ?T++; ?for(int i=1;i<=t;i++)cnt[o^1][i]=0;}inline void add(int x,int y,int z){ ?if(z>=inf)return; ?if(v[o^1][x][y]<T){ ???v[o^1][x][y]=T; ???w[o^1][x][y]=z; ???s[o^1][x][cnt[o^1][x]++]=y; ???return; ?} ?up(w[o^1][x][y],z);}void solve(){ ?for(i=0;i<n;i++)a[i]=i; ?for(i=1;i<1<<n;i++)dp[0][i]=inf; ?while(K--){ ???scanf("%d%d%d",&x,&y,&z);x--,y--; ???must[x]=must[y]=1; ???merge(x,y); ???for(i=0;i<1<<n;i++)dp[o^1][i]=inf; ???for(i=0;i<1<<n;i++)if(dp[o][i]<inf){ ?????up(dp[o^1][i^(1<<x)^(1<<y)],dp[o][i]+z); ?????up(dp[o^1][i],dp[o][i]+z+z); ???} ???o^=1; ?} ?decode(encode()); ?h=1; ?ext(encode()); ?while(h<=t){ ???ll x=q[h]; ???for(i=0;i<n;i++)for(j=0;j<n;j++){ ?????decode(x); ?????merge(i,j); ?????g[h][i][j]=ext(encode()); ???} ???h++; ?} ?scanf("%d",&m); ?for(i=0;i<n;i++)for(j=0;j<n;j++)e[i][j]=inf; ?while(m--){ ???scanf("%d%d%d",&x,&y,&z);x--,y--; ???if(x==y)continue; ???if(x>y)swap(x,y); ???up(e[x][y],z); ?} ?clr(); ?for(i=0;i<1<<n;i++)add(1,i,dp[o][i]); ?o^=1; ?for(x=0;x<n;x++)for(y=0;y<n;y++)if(e[x][y]<inf){ ???z=e[x][y]; ???clr(); ???for(i=1;i<=t;i++)for(j=0;j<cnt[o][i];j++){ ?????int S=s[o][i][j],f=w[o][i][S]; ?????add(i,S,f); ?????add(g[i][x][y],S^(1<<x)^(1<<y),f+z); ?????add(g[i][x][y],S,f+z+z); ???} ???o^=1; ?} ?for(i=1;i<=t;i++)if(check(q[i]))for(j=0;j<cnt[o][i];j++)if(!s[o][i][j])up(ans,w[o][i][0]); ?printf("%d",ans);}}int main(){ ?scanf("%d%d",&n,&K); ?if(!K)return puts("0"),0; ?if(K<=LIM)SMALL::solve();else BIG::solve(); ?return 0;}
BZOJ4479 : [Jsoi2013]吃货jyy
原文地址：http://www.cnblogs.com/clrs97/p/7461211.html