题解 P4716 【【模板】最小树形图】
Great_Influence
2018-06-26 16:13:59
就是模板吧。目前还没找到这个东西除了模板有什么用......
当然，可以用来解决[这道题](https://www.luogu.org/problemnew/show/P3244)(但是和算法本身没有关系)
以下讲的是朱-刘算法，还有神仙Tarjan提出的更快的算法($O(m+nlogn)$)，不过一般用不上就是了。
大体来说，就是发现一个合法的树形图的每个点都只有一条入边~~(废话)~~，所以贪心地对每个点都选择一条通向它的最短的边(没有就没有树形图了)。这样连出来的图有$n-1$条边，但不一定是树。不过，这个图最多只有几个简单环(因为每个点只连入$1$条边)。所以，我们将这些环搜出并缩起来，然后在缩完后的边中继续跑最小树形图直到选择的边构成树。时间复杂度$O(nm)$，但是一般情况会快很多。
注意每次跑一遍算法后，答案已经加上每个点的最短入边了。但是如果要将这条边更换，那么需要将其他的边长减去原来最短入边边长，再继续计算。
然后这道题(以及基本所有的题)只要求这个边权和就可以了，所以就不需要展开之类的操作了。
代码:
```cpp
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i)
#define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i)
#define For(i,a,b) for(i=(a),i<=(b);++i)
#define Forward(i,a,b) for(i=(a),i>=(b);--i)
template<typename T>inline void read(T &x)
{
T f=1;x=0;char c;
for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=x*10+(c^48);
x*=f;
}
inline void write(int u,char ed='\n')
{
if(!u){putchar(48);putchar(ed);return;}
static int sta[43],tp;
for(tp=0;u;u/=10)sta[++tp]=u%10;
for(;tp;putchar(sta[tp--]^48));
putchar(ed);
}
using namespace std;
const int MAXN=111,MAXM=1e4+7;
static int n,m,rt;
static struct edge
{
int u,v,w;
}p[MAXM];
inline void init()
{
read(n);read(m);read(rt);
Rep(i,1,m)read(p[i].u),read(p[i].v),read(p[i].w);
}
static int in[MAXN],pre[MAXN],vis[MAXN],id[MAXN];
const int inf=0x3f3f3f3f;
inline long long getans()
{
static long long ans=0;
static int cnt=0,u,v,laz;
while(1)
{
Rep(i,1,n)in[i]=inf,id[i]=vis[i]=0;
Rep(i,1,m)if(p[i].u^p[i].v&&p[i].w<in[p[i].v])
pre[p[i].v]=p[i].u,in[p[i].v]=p[i].w;
in[rt]=0;
Rep(i,1,n)
{
if(in[i]==inf)return -1;
ans+=in[i];
for(u=i;u^rt&&vis[u]^i&&!id[u];u=pre[u])vis[u]=i;
if(u^rt&&!id[u])
{
id[u]=++cnt;
for(v=pre[u];v^u;v=pre[v])id[v]=cnt;
}
}
if(!cnt)return ans;
Rep(i,1,n)if(!id[i])id[i]=++cnt;
Rep(i,1,m)
{
laz=in[p[i].v];
if((p[i].u=id[p[i].u])^(p[i].v=id[p[i].v]))
p[i].w-=laz;
}
n=cnt;rt=id[rt];cnt=0;
}
}
inline void solve(){printf("%lld\n",getans());}
int main()
{
init();
solve();
return 0;
}
```