题目
题目大意
给你一个图，让你选择权值和最小的边，使得(1)和(n)，(2)和(n-1)，……，(K)和(n-K+1)联通。
(Kleq 4)
思考历程
一看到这题就觉得特别神仙……
然后去思考网络流……
搞出了一个最小割，后来发现这是错的……
匆匆打了个表，获得了这题的十分之一的分数。
正解
其实这题有水法，许多人是全排列+(SPFA)，跑了一遍之后将路过的边清(0)，继续跑。这样贪心显然是错的，反例也有，但是极其水的数据居然给了他们(100)分！
正解是DP。
题解中有个叫做(stenir tree)的东西，感觉似乎很强大。当然我不懂，我只会DP。
现在我们是要求出一个最小生成森林，使得一些点对联通。
考虑一棵树。显然，树的叶子节点一定是要求联通的节点（反过来倒不一定）。
于是我们就试着DP……
设(f_{S,i})表示当前这棵树的根节点为(i)，并且(S)集合中的所有点连在了一起的最小代价
转移的时候就是两棵树的根节点连在一起，也就是(f_{S',i}+w(i,j)+f_{S-S',j} o f_{S,i})
(S')是(S)的子集。（枚举(S)和(S')的时间复杂度是(3^k)的，(k)表示位数，具体实现比较巧妙，见代码）
然后这道题就差不多完了。注意，转移的时候一般是(S)从低到高转移，但也会向(S)相等的状态转移，这就意味着会有后效性。所以，对于同层的转移，我们特殊地用最短路算法来处理。
代码
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
inline void update(int &a,int b){a>b?a=b:0;}
#define N 10010
#define M 10010
int n,m,K;
struct EDGE{
int to,len;
EDGE *las;
} e[M*2];
int ne;
EDGE *last[N];
inline void link(int u,int v,int len){
e[ne]={v,len,last[u]};
last[u]=e+ne++;
}
int f[256][N],*dis;
struct Node{
int x,dis;
} h[1000001];
int nh;
inline bool cmph(const Node &son,const Node &fa){
return son.dis>fa.dis;
}
int mn[256],ans[256];
inline bool ok(int s){
for (int i=0;i<K;++i)
if ((s>>i&1)^(s>>i+K&1))
return 0;
return 1;
}
int main(){
freopen("in.txt","r",stdin);
scanf("%d%d%d",&n,&m,&K);
for (int i=1;i<=m;++i){
int u,v,len;
scanf("%d%d%d",&u,&v,&len);
link(u,v,len),link(v,u,len);
}
memset(f,63,sizeof f);
for (int i=1;i<=K;++i)
f[1<<i-1][i]=f[1<<K+i-1][n-i+1]=0;
for (int i=K+1;i<=n-K;++i)
f[0][i]=0;
for (int s=1;s<1<<K*2;++s){
for (int i=1;i<=n;++i)
for (int s1=(s-1)&s;s1;s1=(s1-1)&s)
if (f[s1][i]<0x3f3f3f3f)
for (EDGE *ei=last[i];ei;ei=ei->las)
update(f[s][i],f[s1][i]+ei->len+f[s-s1][ei->to]);
dis=f[s];
nh=0;
for (int i=1;i<=n;++i)
h[nh++]={i,dis[i]};
while (nh){
int x=h[0].x,disx=h[0].dis;
pop_heap(h,h+nh--,cmph);
if (disx>dis[x])
continue;
for (EDGE *ei=last[x];ei;ei=ei->las)
if (disx+ei->len<dis[ei->to]){
dis[ei->to]=disx+ei->len;
h[nh++]={ei->to,dis[ei->to]};
push_heap(h,h+nh,cmph);
}
}
mn[s]=INT_MAX;
for (int i=1;i<=n;++i)
update(mn[s],dis[i]);
}
memset(ans,63,sizeof ans);
ans[0]=0;
for (int s=1;s<1<<K*2;++s)
for (int s1=s;s1;s1=(s1-1)&s)
if (ok(s-s1) && ok(s1))
update(ans[s],ans[s-s1]+mn[s1]);
if (ans[(1<<K*2)-1]<0x3f3f3f3f)
printf("%d
",ans[(1<<K*2)-1]);
else
printf("-1
");
return 0;
}
总结
不是什么题都能用网络流做的……
DP也能玩出各种花样……