Description
村子间的小路年久失修，为了保障村子之间的往来，法珞决定带领大家修路。对于边带权的无向图 G = (V, E)，
请选择一些边，使得1 <= i <= d， i号节点和 n - i + 1 号节点可以通过选中的边连通，最小化选中的所有边
的权值和。
Input
第一行两个整数 n, m，表示图的点数和边数。接下来的 m行，每行三个整数 ui, vi, wi，表示有一条 ui 与 vi
之间，权值为 wi 的无向边。
1 <= d <= 4
2d <= n <= 10^4
0 <= m <= 10^4
1 <= ui, vi <= n
1 <= wi <= 1000
Output
一行一个整数，表示答案，如果无解输出-1
Sample Input
10 20 1 6 5 1 6 9 4 9 4 2 9 4 10 6 1 2 2 3 6 7 6 10 5 7 1 9 7 2 5 9 10 1 6 8 4 7 4 5 7 1 2 6 9 10 10 6 8 7 2 10 9 10 1 2 4 10 1 8 9 9 7
Sample Output
8
好像是个斯坦纳树的模板题。。。
虽然到现在也不知道斯坦纳树具体是个什么玩意，，，大概就是能处理有后效性的图上状压dp ???
因为关键点很少，所以可以状压dp。
设f(S,i)为目前选的边的构成的树的根是i，且关键点集合状态是S的最优值。
转移有两种：
1. f(S,i)=min{f(s,i)+f(S^s,i)},其中s是S的子集。
相当于合并两颗树(如果有重复边也不要紧，因为有重复边的话最后一定不会在最优答案中)
2.f(S,i)=min{f(S,x)+val(x,i)}，其中x与i有边相连。
相当于将树根扩展出去一个节点。
最后再根据f数组进行子集dp，只能从满足条件的子集转移(即有i号节点必须有n-i+1号节点)
/************************************************************** Problem: 4774 User: JYYHH Language: C++ Result: Accepted Time:2180 ms Memory:14904 kb****************************************************************/ #include#include #include #include #include #define ll long longusing namespace std;int f[300][10005],n,m,hd[10005],d;int to[20005],val[20005],ne[20005];int dis[10005],ans[300],num,ci[20],all;bool iq[10005];int q[400005],l,r;int main(){ memset(f,0x3f,sizeof(f)); memset(ans,0x3f,sizeof(ans)); ci[0]=1; for(int i=1;i<=10;i++) ci[i]=ci[i-1]<<1; scanf("%d%d%d",&n,&m,&d); int uu,vv,ww; for(int i=1;i<=m;i++){ scanf("%d%d%d",&uu,&vv,&ww); to[++num]=vv,ne[num]=hd[uu],hd[uu]=num,val[num]=ww; to[++num]=uu,ne[num]=hd[vv],hd[vv]=num,val[num]=ww; } for(int i=1;i<=d;i++) f[ci[i-1]][i]=0; for(int i=n-d+1;i<=n;i++) f[ci[n+d-i]][i]=0; memset(f[0],0,sizeof(f[0])); all=ci[d<<1]-1; for(int S=1;S<=all;S++){ for(int i=1;i<=n;i++) for(int s=(S-1)&S;s;s=(s-1)&S) f[S][i]=min(f[S][i],f[s][i]+f[s^S][i]); for(int i=1;i<=n;i++) dis[i]=f[S][i],q[i]=i,iq[i]=1; l=1,r=n; while(l<=r){ int x=q[l++]; for(int i=hd[x];i;i=ne[i]) if(dis[x]+val[i]