在不务正业大半年后继续开始写正经的解题报告……
题目链接:
题意:
一个N<=50,M<=1000的边带权无向图,给定K<=5,第1~K号点是住宅,第N-K+1~N号点是避难所。要求选出一些边,把它们连起来,使得每个住宅都能走到一个避难所(注意一个避难所只能给一个住宅用),求最小的权值之和。
斯坦纳树:
这道题是基于斯坦纳树的。斯坦纳树的定义是:给定一张图和一个顶点集合,要求选出一些边,使得集合中的顶点连通。显然最小生成树是斯坦纳树的一个特殊情况:集合就是整个顶点集合V。
可以用状压DP求解斯坦纳树:令f[i][s]=(以i为根,集合中顶点连通情况至少为s的最小代价)。
首先从小到大枚举s转移。有两种转移方式:
1. f[i][s]=min(f[i][s], f[i][t]+f[i][s-t]),要求t是s的子集。枚举i和t即可完成。 枚举t可以用:for(t=s;t;t=(t-1)&s)。这个转移的意思是,将以i为根的两棵树“拼”起来。
2. f[i][s]=min(f[i][s], f[j][s]+w(i,j)),要求i,j之间有连边。这个意思是从j这个根往外“长”。
第二种转移比较麻烦,因为没有一个确定的顺序。怎么办呢?SPFA。在第一种转移结束后,建超级源S,向每个点连边w(S,i)=f[i][s],原图中的边保持不变。然后从超级源S开始做一次最短路,就可以把第二种转移搞定了。
题解:
我们的这道题基本就是斯坦纳树。但还有一小点不同:最后不一定是所有的住宅&避难所都在同一个联通块中。例如:住宅1,2和避难所8,9连通,住宅3和避难所10连通,这也是符合基本法的,可以作为一组解。
怎么办呢?在求完斯坦纳树之后,额外再进行一次“子集合并”的DP,注意,这里所有的合法状态都必须是住宅数=避难所数的。
代码:
#include#include #include #include #include #include using namespace std; const int INF=0x7fffffff/2; const int SIZEN=60; int N,M,K; vector > c[SIZEN]; void SPFA(int S,int dis[]){ static bool inq[SIZEN]; static queue Q; for(int i=0;i<=N;i++) inq[i]=false,dis[i]=INF; while(!Q.empty()) Q.pop(); dis[S]=0;Q.push(S);inq[S]=true; while(!Q.empty()){ int x=Q.front();Q.pop();inq[x]=false; for(int i=0;i 由于忘掉“No Solution”,WA掉一次……