主题链接:http://acm.hdu.edu.cn/showproblem.php?
pid=4085
由于这题专门花一晚上学习斯坦纳树。找到比較好的学习资料,链接在这里:http://endlesscount.blog.163.com/blog/static/821197872012525113427573/
花了非常长时间照着别人写了一份自己风格的代码,慢慢理解:
/* *********************************************** Author :rabbit Created Time :2014/7/16 20:45:31 File Name :1.cpp ************************************************ */ #pragma comment(linker, "/STACK:102400000,102400000") #include <stdio.h> #include <iostream> #include <algorithm> #include <sstream> #include <stdlib.h> #include <string.h> #include <limits.h> #include <string> #include <time.h> #include <math.h> #include <queue> #include <stack> #include <set> #include <map> using namespace std; #define INF 100000000 #define eps 1e-8 #define pi acos(-1.0) typedef long long ll; const int maxn=60; struct Edge{ int next,to,val; }edge[2100]; int head[maxn],tol,n,m,K; int s[maxn],in[maxn][1<<10],d[maxn][1<<10],dp[1<<10]; void addedge(int u,int v,int c){ edge[tol].to=v; edge[tol].next=head[u]; edge[tol].val=c; head[u]=tol++; } bool check(int x){ int r=0; for(int i=0;x;i++,x>>=1) r+=(x&1)*(i<K?1:-1); return r==0; } int main() { //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); int T; cin>>T; while(T--){ memset(head,-1,sizeof(head));tol=0; memset(in,0,sizeof(in)); memset(s,0,sizeof(s)); scanf("%d%d%d",&n,&m,&K); int nn=1<<(2*K); for(int i=1;i<=n;i++) for(int j=0;j<nn;j++) d[i][j]=INF; while(m--){ int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } for(int i=1;i<=K;i++){ s[i]=1<<(i-1),d[i][s[i]]=0; s[n-i+1]=1<<(K+i-1),d[n-i+1][s[n-i+1]]=0; } for(int y=0;y<nn;y++){ queue<int> Q; for(int x=1;x<=n;x++){ for(int i=(y-1)&y;i;i=(i-1)&y) d[x][y]=min(d[x][y],d[x][i|s[x]]+d[x][(y-i)|s[x]]); if(d[x][y]<INF)Q.push(x*10000+y),in[x][y]=1; } while(!Q.empty()){ int x=Q.front()/10000,y=Q.front()%10000; in[x][y]=0; Q.pop(); for(int i=head[x];i!=-1;i=edge[i].next){ int v=edge[i].to; if(d[v][y|s[v]]>d[x][y]+edge[i].val){ d[v][y|s[v]]=d[x][y]+edge[i].val; if(y==(y|s[v])&&!in[v][y]){ in[v][y]=1; Q.push(10000*v+y); } } } } } for(int j=0;j<nn;j++){ dp[j]=INF; for(int i=1;i<=n;i++) dp[j]=min(dp[j],d[i][j]); } for(int i=1;i<nn;i++) if(check(i)) for(int j=i&(i-1);j;j=(j-1)&i) if(check(j)) dp[i]=min(dp[i],dp[j]+dp[i-j]); if(dp[nn-1]>=INF)puts("No solution"); else printf("%d ",dp[nn-1]); } return 0; }
版权声明:本文博客原创文章,博客,未经同意,不得转载。