HDU 4085 Steiner树

主题链接：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;
}