标签：10 int namespace 最小 树形图 ri getchar
最小树形图
- 求最短弧集合 \(E\)
找到每个 \(u\) 点的最小入边 \(in[u]\) ，如果存在非根节点没有入边，则一定不存在树形图
for(ri int i=1;i<=m;++i){
if(e[i].u^e[i].v&&e[i].w<in[e[i].v]){
in[e[i].v]=e[i].w,pre[e[i].v]=e[i].u;
}
}
for(ri int i=1;i<=n;++i) if(i^rt&&!pre[i]) return -1;
- 判断集合 \(E\) 中有没有有向环，如果有转步骤 \(3\) ，否则转 \(4\)
一定要记录 \(cnt\) 或开一个 \(bool\) 数组记录走过的边，不然可能疯狂走环；
cnt=in[rt]=0;
for(ri int i=1,v;i<=n;++i){
as+=in[v=i];
while(vs[v]^i&&!id[v]&&v^rt) vs[v]=i,v=pre[v];
if(!id[v]&&v^rt){
id[v]=++cnt,v=pre[v];
while(!id[v]) id[v]=cnt,v=pre[v];
}
}
if(!cnt) break;
- 收缩点，把有向环收缩成一个点，并且对图重新构建，包括边权值的改变和点的处理，之后再转步骤 \(1\)
对于环外指向环的边 \((u \to v, w)\) ，其边权变为 \(w-in[v]\)
for(ri int i=1;i<=n;++i) if(!id[i]) id[i]=++cnt;
for(ri int i=1;i<=m;++i){
if(id[e[i].u]^id[e[i].v]) e[i].w-=in[e[i].v];
e[i].u=id[e[i].u],e[i].v=id[e[i].v];
}
rt=id[rt],n=cnt;
- 展开收缩点，求得最小树形图
如果不需要输出具体方案，直接返回 \(ans\) 即可
code
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
using namespace std;
namespace Q{
il int rd(){
ri int x=0;ri bool f=0;ri char c=getchar();
while(c^EOF&&!isdigit(c)) f|=(c==45),c=getchar();
while(c^EOF&&isdigit(c)) x=x*10+(c^48),c=getchar();
return f?-x:x;
}
il void wt(int x){
if(x<0) x=-x,putchar(45);
if(x>=10) wt(x/10);
return putchar(x%10|48),void();
}
} using namespace Q;
cs int N=105,M=10004,inf=1<<30;
int in[N],pre[N],id[N],n,m,rt,vs[N];
struct qwq{int u,v,w;}e[M];
il int calc(){
ri int as=0,cnt=0;
while(1){
for(ri int i=1;i<=n;++i) in[i]=inf,pre[i]=vs[i]=id[i]=0;
for(ri int i=1;i<=m;++i){
if(e[i].u^e[i].v&&e[i].w<in[e[i].v]){
in[e[i].v]=e[i].w,pre[e[i].v]=e[i].u;
}
}
for(ri int i=1;i<=n;++i) if(i^rt&&!pre[i]) return -1;
cnt=in[rt]=0;
for(ri int i=1,v;i<=n;++i){
as+=in[v=i];
while(vs[v]^i&&!id[v]&&v^rt) vs[v]=i,v=pre[v];
if(!id[v]&&v^rt){
id[v]=++cnt,v=pre[v];
while(!id[v]) id[v]=cnt,v=pre[v];
}
}
if(!cnt) break;
for(ri int i=1;i<=n;++i) if(!id[i]) id[i]=++cnt;
for(ri int i=1;i<=m;++i){
if(id[e[i].u]^id[e[i].v]) e[i].w-=in[e[i].v];
e[i].u=id[e[i].u],e[i].v=id[e[i].v];
}
rt=id[rt],n=cnt;
}
return as;
}
signed main(){
n=rd(),m=rd(),rt=rd();
for(ri int i=1;i<=m;++i){
e[i].u=rd(),e[i].v=rd(),e[i].w=rd();
}
wt(calc());
return 0;
}
标签：10,
int,
namespace,
最小,
树形图,
ri,
getchar
From： https://www.cnblogs.com/windymoon/p/17259265.html