最小树形图
朱刘算法
- 【百度百科】
- 问题引入：
给你个点条边的有向图，边有边权，给定一个根，你可以选择一些边，求以给定根为根的有向生成树的最小代价（有向生成树就是边的方向为父亲指向儿子）。
- 分析：
当然，有向的话我们不能用最小生成树算法了。
我们要先提前判断一下图的连通性（如果不连通也就不存在最小树形图了）。
现在，我们要找出一个使得一个有向图连通的最小权值的（一般为边权和，有时会有点权，而且有可能点权会随着边的选择变化）有根树，那么可以贪心的考虑，我们对于个点的图，我们选出每个点入边中权值最小的一条边然后看能不能构成一棵树。
因为个点会选出条边（当然我们不选根的入边），如果这个点条边组成的新图没有环，那么当前肯定就是答案了。否则有环的话当前的图肯定不连通，所以我们通过缩环，构成新的图然后重复上面的操作来找，直到没有环。
但是一个环，你肯定是要用一条边换掉环上的一条边，使其成为树。我们可以在缩完环后，直接枚举边，然后将权值更新为减去当前的去的点的最小入边。
重复这样的操作，最后得到的就是答案啦。
复杂度最坏为（为点数为边数）,但是tarjan神仙有的做法，蒟蒻没找到，希望有大神教教蒟蒻，QAQ
（先简略的说明一下，后面再填坑填详细一点）
下面给出洛谷模板题代码,仅供参考【题目IN洛谷】
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int M=1e5+10;
const int inf=0x7fffffff;
int n,m,root;
int low[M],f[M],bel[M],vis[M];
int fa[M];
int find(int a){return fa[a]==a?a:fa[a]=find(fa[a]);}
void merge(int a,int b){
a=find(a);b=find(b);
if(a!=b)fa[a]=b;
}
bool check(){
int a=find(1);
for(int i=2;i<=n;i++){
if(find(i)!=a) return 0;
}
return 1;
}
struct ss{
int u,v,w;
ss(){}
ss(int a,int b,int c):u(a),v(b),w(c){}
}e[M];
int cnt;
int min_g(){
int k,ans=0;
if(!check()) return -1;//判断连通
while(1){
for(int i=1;i<=n;i++)low[i]=inf,vis[i]=f[i]=bel[i]=0;
for(int i=1;i<=m;i++){
if(e[i].u!=e[i].v&&e[i].w<low[e[i].u]){
f[e[i].u]=e[i].v;
low[e[i].u]=e[i].w;
}//找最小入边
}
low[root]=cnt=0;
for(int i=1;i<=n;i++)if(low[i]==inf) return -1;
for(int i=1;i<=n;i++){
ans+=low[i];
//加入答案并找出环
for(k=i;((!bel[k])&&(vis[k]!=i)&&(k!=root));k=f[k])vis[k]=i;
if((k!=root)&&!bel[k]){
bel[k]=++cnt;
for(int j=f[k];j!=k;j=f[j])bel[j]=cnt;
}
}
if(!cnt) return ans;//没有环了就是答案
for(int i=1;i<=n;i++)if(!bel[i])bel[i]=++cnt;//缩环，重新编号
for(int i=1;i<=m;i++){
if(e[i].u!=e[i].v)e[i].w-=low[e[i].u];//更新为差值，因为每次都是加上了的，所以换一条边相当于再加上差值
e[i].v=bel[e[i].v];e[i].u=bel[e[i].u];
}
n=cnt;root=bel[root];//重新给点数和根赋值
}
return ans;
}
int a,b,c,tc;
int main(){
scanf("%d%d%d",&n,&m,&root);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
++tc;
scanf("%d%d%d",&e[tc].v,&e[tc].u,&e[tc].w);
if(e[tc].u==root)--tc;//有根的边不要。
else merge(e[tc].u,e[tc].v);
}
m=tc;
printf("%d
",min_g());
return 0;
}
另外一道类似的模板题
BZOJ4349【IN】
双倍经验【IN】
#include<cstdio>
#include<cstring>
#include<algorithm>
#define db double
#define inf 1e20
using namespace std;
const int M=2e4+10;
int f[M],bel[M],vis[M];
int n,m,nm,tot,id[M],times[M],root;
db lowest[M],cost[M],ans;
struct ss{
int u,v;db w;
ss(){}
ss(int a,int b,db c):u(a),v(b),w(c){}
}g[M];
void min_gt(){
int k,cnt=0;
while(1){
for(int i=1;i<=n;i++)lowest[i]=inf,f[i]=bel[i]=vis[i]=0;
for(int i=1;i<=m;i++){
if(g[i].v!=g[i].u&&g[i].w<lowest[g[i].u])
f[g[i].u]=g[i].v,lowest[g[i].u]=g[i].w;
}
lowest[root]=0;cnt=0;
for(int i=1;i<n;i++){
ans+=lowest[i];
for(k=i;((!bel[k])&&(vis[k]!=i)&&(k!=root));k=f[k])vis[k]=i;
if((k!=root)&&(!bel[k])){
bel[k]=++cnt;
for(int j=f[k];j!=k;j=f[j])bel[j]=cnt;
}
}
if(!cnt)return;
for(int i=1;i<=n;i++)if(!bel[i])bel[i]=++cnt;
for(int i=1;i<=m;i++){
db now=lowest[g[i].u];
g[i].v=bel[g[i].v];g[i].u=bel[g[i].u];
if(g[i].u!=g[i].v)g[i].w-=now;
}
n=cnt;root=bel[root];
}
}
db a;int b,c;
int main(){
scanf("%d",&n);
//0~n-1，新建超级根n
for(int i=1;i<=n;++i){
scanf("%lf%d",&a,&b);
if(b){
id[i]=++tot;lowest[tot]=inf;
cost[tot]=a;times[tot]=b;
g[tot].u=tot;g[tot].w=a;
}
}
n=tot+1;root=n;m=tot;
for(int i=1;i<n;i++)g[i].v=n,lowest[i]=cost[i];
scanf("%d",&nm);
for(int i=1;i<=nm;i++){
scanf("%d%d%lf",&b,&c,&a);
if(!id[b]||!id[c]||b==c) continue;
g[++m].v=id[b];g[m].u=id[c];g[m].w=a;
lowest[g[m].u]=min(lowest[g[m].u],a);
}
for(int i=1;i<n;i++)if(times[i]>1)ans+=(times[i]-1)*lowest[i];
min_gt();
printf("%.2lf
",ans);
return 0;
}