定义
最小树形图就是有向边的最小生成树。
朱刘算法
我们先考虑有根的情况。
可以想到的是，我们可以对于每一个非根的点选出一个权值最小的入边。在没有环的情况下这就是最优答案。考虑有环，可以想到的是，我们需要拆开环上的一条边然后继续搞。我们使用反悔贪心，先把环缩成一个点，再把以前指向这个环上某个点的边权减去那个点在环上连上的边权。接着继续迭代。
正确性显然，时间复杂度 (Theta(nm))。
Code
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define inf 0x7f7f7f7f
#define int long long
#define MAXM 10005
#define MAXN 105
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
int n,m,r,ans,id[MAXN],pre[MAXN],ine[MAXN],vis[MAXN];
struct edge{
int u,v,w;
}e[MAXM];
signed main(){
read (n,m,r);
for (Int i = 1;i <= m;++ i) read (e[i].u,e[i].v,e[i].w);
while (1){
int ind = 0;memset (ine,0x7f,sizeof (ine));
for (Int i = 1;i <= m;++ i)
if (e[i].u != e[i].v && e[i].w < ine[e[i].v])
ine[e[i].v] = e[i].w,pre[e[i].v] = e[i].u;
for (Int i = 1;i <= n;++ i) if (i != r && ine[i] == ine[0]) return puts ("-1"),0;else vis[i] = id[i] = 0;
for (Int i = 1;i <= n;++ i) if (i ^ r){
ans += ine[i];int now = i;
while (vis[now] != i && !id[now] && now != r) vis[now] = i,now = pre[now];
if (!id[now] && now != r){
id[now] = ++ ind;
for (Int u = pre[now];u != now;u = pre[u]) id[u] = ind;
}
}
if (!ind) return write (ans),putchar ('
'),0;
for (Int i = 1;i <= n;++ i) if (!id[i]) id[i] = ++ ind;
for (Int i = 1,tmp;i <= m;++ i){
tmp = ine[e[i].v],e[i].u = id[e[i].u],e[i].v = id[e[i].v];
if (e[i].u ^ e[i].v) e[i].w -= tmp;
}
r = id[r],n = ind;
}
return 0;
}
Tarjan 优化朱刘算法
我们可以想到另外一种方法来求。
我们每次加入最小的一个边，然后我们每次有环的时候，我们就把环缩成一个点。时间复杂度不变。
考虑优化。我们可以对于每一个点维护一个左偏树，维护连向它的边。我们每次选出连向它的边最小的边，然后在原图中加入，也即是在左偏树中删去。为了方便，我们可以这个时候就判断我们是否可能构成环，如果可以构成环，我们就把这个环都缩成一个点，把左偏树都合并起来，再在原图中加入构成环的那条边。需要注意的是，你可能缩了环之后还可能继续构成环。
对于缩点，我们可以使用并查集，然后对于找环，我们再用一个并查集就好了。
时间复杂度 (Theta((n+m)log m))。
Code
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define MAXN 100005
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
int n,m,r;
struct node{
int u,w,dep,tag;
void operator += (int p){w += p,tag += p;}
}tree[MAXN];
int lson[MAXN],rson[MAXN];
void Pushdown (int x){
tree[lson[x]] += tree[x].tag,tree[rson[x]] += tree[x].tag,tree[x].tag = 0;
}
int Merge (int x,int y){
if (!x || !y) return x + y;
if (tree[x].w > tree[y].w) swap (x,y);
Pushdown (x),Pushdown (y),rson[x] = Merge (rson[x],y);
if (tree[lson[x]].dep < tree[rson[x]].dep) swap (lson[x],rson[x]);
tree[x].dep = tree[rson[x]].dep + 1;
return x;
}
void pop (int &x){
tree[x].tag -= tree[x].w,tree[x].w = 0,Pushdown (x),x = Merge (lson[x],rson[x]);
}
int findSet (int fa[],int x){return fa[x] == x ? x : fa[x] = findSet (fa,fa[x]);}
struct edge{
int u,w;
bool operator < (const edge &p)const{return w > p.w;}
};
priority_queue <edge> q;
#define RT(u) tree[root[u]].u
#define RTW(u) tree[root[u]].w
int root[MAXN],f[MAXN],g[MAXN],fa[MAXN];
signed main(){
read (n,m,r);
for (Int i = 1;i <= n;++ i) f[i] = g[i] = i;
for (Int i = 1,u,v,w;i <= m;++ i){
read (u,v,w);
if (v == r) continue;
tree[i] = node {u,w,1,0},root[v] = Merge (root[v],i);
}
for (Int i = 1;i <= n;++ i) if (i ^ r){
if (!root[i]) return puts ("-1"),0;
q.push (edge {i,RTW(i)});
}
int ans = 0;
for (Int i = 1;i <= n - 1;++ i){
while (!q.empty()){
edge now = q.top();
if (now.w != RTW(now.u)) q.pop ();
else break;
}
if (q.empty()) return puts ("-1"),0;
int u = q.top().u;ans += q.top().w,q.pop ();
f[u] = findSet (f,fa[u] = RT(u)),pop (root[u]),u = f[u];
if (!root[u]) continue;
int s = 0;
while (findSet (f,RT(u)) == u){
int v = findSet (g,RT(u));
s += RTW(u),pop (root[u]);
for (;v ^ u;g[v] = u,v = findSet (g,fa[v])) root[u] = Merge (root[u],root[v]);
}
if (!root[u]) continue;
tree[root[u]] += s,q.push (edge {u,RTW(u)});
//你这里边权都加上s的原因是因为你选了这些边还没有加边权，你之后如果要加进去就必须考虑到
}
write (ans),putchar ('
');
return 0;
}