处理这样一类问题：
给一个有向图，定义树形图：一个有向图以x为根的树形图，是一个n-1条边的集合，使得x能到达其他每一个点
树形图的权值定义为边的和
朱刘算法就是求最小树形图
方法：
1.给每个点p找一个边权最小的连向它的边，边权为val，前驱设为pre。找到了一个边集E0
ans记录总权值
2.检查，如果有一个孤立点（除了rt），那么无解，退出
如果没有有向环，那么完毕。当前的ans就是答案。退出
3.对于每一个有向环，缩点
4.更新新图的权值：枚举所有的边，如果x，y缩点之后不是一个点，那么e[i].v-=val[y]，象征，如果再选择这个点，那么就把环上的这个边删掉。
重复以上过程，直到退出
（5.如果要输出方案，那么在没有有向环之后，要把缩的点再展开大概用边来记录替换的信息，递归处理就可以吧，，，）
复杂度：O(nm)可能远远不到这个上界
正确性：由于有反悔操作，所以直接贪心就正确了。
代码：
poj3164 Command Network
不能用快读，否则会TLE。。。辣鸡poj
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;x=0;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*10+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=105;
const int M=1e5+5;
const int inf=2000000000;
struct node{
int x,y;
double v;
}e[M];
int id[N],vis[N],pre[N];
double val[N];
double px[N],py[N];
int n,m;
double ans;
int cnt;
double dist(int a,int b){
return sqrt((double)(px[a]-px[b])*(px[a]-px[b])+(double)(py[a]-py[b])*(py[a]-py[b]));
}
double wrk(int rt,int n){
double ret=0;
// printf("%.10lf",val[0]);
int turn=0;
while(1){
++turn;
// cout<<" turn "<<turn<<" "<<n<<" rt "<<rt<<endl;
for(reg i=0;i<n;i++) val[i]=inf;
for(reg i=0;i<m;++i){
if(e[i].x!=e[i].y){
if(val[e[i].y]>e[i].v){
val[e[i].y]=e[i].v;
pre[e[i].y]=e[i].x;
}
}
}
for(reg i=0;i<n;++i){
//cout<<i<<" : "<<pre[i]<<" : "<<val[i]<<endl;
if(i==rt) continue;
if(val[i]==inf) return -1;
}
cnt=0;
memset(id,-1,sizeof id);
memset(vis,-1,sizeof vis);
val[rt]=0.00;
for(reg i=0;i<n;++i){
//cout<<" start "<<i<<endl;
ret+=val[i];
int v=i;
while(vis[v]!=i&&id[v]==-1&&v!=rt){
vis[v]=i;
v=pre[v];
//cout<<" vv "<<v<<endl;
}
if(v!=rt&&id[v]==-1){
//cout<<" new "<<endl;
for(reg u=pre[v];u!=v;u=pre[u]) id[u]=cnt;
id[v]=cnt++;
}
}
if(cnt==0) break;
// cout<<" after dfs "<<cnt<<endl;
for(reg i=0;i<n;++i) if(id[i]==-1) id[i]=cnt++;
//for(reg i=1;i<=n;++i) cout<<i<<" -- "<<id[i]<<endl;
for(reg i=0;i<m;++i){
int x=e[i].x;
int y=e[i].y;
e[i].x=id[x];
e[i].y=id[y];
if(id[x]!=id[y]) e[i].v-=val[y];
}
//cout<<" endneenndd "<<ret<<" cnt "<<cnt<<endl;
n=cnt;
rt=id[rt];
}
return ret;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(reg i=0;i<n;i++){
scanf("%lf%lf",&px[i],&py[i]);
}
for(reg i=0;i<m;++i){
scanf("%d%d",&e[i].x,&e[i].y);
--e[i].x;
--e[i].y;
//if(x==y) continue;
if(e[i].x!=e[i].y)e[i].v=dist(e[i].x,e[i].y);
else e[i].v=inf;
// cout<<" x y z "<<x<<" "<<y<<" "<<e[lp].v<<endl;
}
ans=wrk(0,n);
if(ans==-1){
printf("poor snoopy
");
}else{
printf("%.2f
",ans);
}
}
return 0;
}
}
signed main(){
// freopen("data.in","r",stdin);
// freopen("my.out","w",stdout);
Miracle::main();
return 0;
}
/*
Author: *Miracle*
Date: 2019/1/7 17:25:32
*/
或者可以用dfs判环，类似tarjan
复杂度一定有保证：
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;x=0;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*10+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=105;
const int M=1e4+5;
struct node{
int x,y;
double v;
}e[M];
int id[N],vis[N],pre[N];
bool in[N];
double val[N];
double px[N],py[N];
int n,m;
double ans;
int sta[N],top;
int cnt;
double dist(int a,int b){
return sqrt((double)(px[a]-px[b])*(px[a]-px[b])+(double)(py[a]-py[b])*(py[a]-py[b]));
}
void dfs(int x){
// cout<<" x "<<x<<endl;
sta[++top]=x;in[x]=1;
vis[x]=1;
if(pre[x]==1) return;
else if(!vis[pre[x]]) dfs(pre[x]);
else if(in[pre[x]]){
// cout<<" new huan "<<endl;
int z;
++cnt;
do{
z=sta[top];
id[z]=cnt;
in[z]=0;
top--;
}while(z!=pre[x]);
}
}
double wrk(int n){
double ret=0;
int rt=1;
memset(val,0x7f,sizeof val);
int turn=0;
while(1){
++turn;
// cout<<" turn "<<turn<<" "<<n<<endl;
memset(vis,0,sizeof vis);
memset(id,0,sizeof id);
memset(in,0,sizeof in);
memset(pre,0,sizeof pre);
memset(val,0x7f,sizeof val);
top=0;cnt=1;
id[1]=cnt;
for(reg i=1;i<=m;++i){
if(e[i].x!=e[i].y&&e[i].y!=rt){
if(val[e[i].y]>e[i].v){
val[e[i].y]=e[i].v;
pre[e[i].y]=e[i].x;
}
}
}
// for(reg i=1;i<=n;++i){
// cout<<i<<" : "<<pre[i]<<" : "<<val[i]<<endl;
// }
val[rt]=0.00;
for(reg i=2;i<=n;++i){
ret+=val[i];
if(i!=rt&&!pre[i]) return -23333;
if(!vis[i]) {
//cout<<" go "<<i<<endl;
top=0;dfs(i);
while(top) in[sta[top--]]=0;
}
}
//cout<<" after dfs "<<cnt<<endl;
for(reg i=2;i<=n;++i) if(!id[i]) id[i]=++cnt;
// for(reg i=1;i<=n;++i) cout<<i<<" -- "<<id[i]<<endl;
if(cnt==n) break;
for(reg i=1;i<=m;++i){
if(id[e[i].x]!=id[e[i].y]){
//cout<<" cut "<<e[i].x<<" "<<e[i].y<<" "<<e[i].v<<endl;
e[i].v-=val[e[i].y];
}
e[i].x=id[e[i].x];
e[i].y=id[e[i].y];
}
//cout<<" endneenndd "<<ret<<" cnt "<<cnt<<endl;
n=cnt;
}
return ret;
}
void clear(){
ans=0;
}
int main(){
while(scanf("%d",&n)!=EOF){
scanf("%d",&m);
int lp=0;
clear();
for(reg i=1;i<=n;++i){
scanf("%lf%lf",&px[i],&py[i]);
}
int x,y;
for(reg i=1;i<=m;++i){
scanf("%d%d",&x,&y);
if(x==y) continue;
if(y==1) continue;
e[++lp].x=x;e[lp].y=y;e[lp].v=dist(x,y);
// cout<<" x y z "<<x<<" "<<y<<" "<<e[lp].v<<endl;
}
m=lp;
ans=wrk(n);
if(ans==-23333){
puts("poor snoopy");
}else{
printf("%.2f
",ans);
}
}
return 0;
}
}
signed main(){
Miracle::main();
return 0;
}
/*
Author: *Miracle*
Date: 2019/1/7 17:25:32
*/
正常一点的模板：
luoguP4716 【模板】最小树形图
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;x=0;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*10+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=105;
const int M=1e4+5;
struct node{
int x,y;
int v;
}e[M];
int id[N],vis[N],pre[N];
bool in[N];
int val[N];
int n,m;
int rt;
int sta[N],top;
int cnt;
void dfs(int x){
// cout<<" x "<<x<<endl;
sta[++top]=x;in[x]=1;
vis[x]=1;
if(pre[x]==rt) return;
else if(!vis[pre[x]]) dfs(pre[x]);
else if(in[pre[x]]){
// cout<<" new huan "<<endl;
int z;
++cnt;
do{
z=sta[top];
id[z]=cnt;
in[z]=0;
top--;
}while(z!=pre[x]);
}
}
double wrk(int n){
int ret=0;
int turn=0;
while(1){
++turn;
// cout<<" turn "<<turn<<" "<<n<<endl;
memset(vis,0,sizeof vis);
memset(id,0,sizeof id);
memset(in,0,sizeof in);
memset(pre,0,sizeof pre);
memset(val,0x3f,sizeof val);
top=0;cnt=1;
id[rt]=cnt;
for(reg i=1;i<=m;++i){
if(e[i].x!=e[i].y&&e[i].y!=rt){
if(val[e[i].y]>e[i].v){
val[e[i].y]=e[i].v;
pre[e[i].y]=e[i].x;
}
}
}
// for(reg i=1;i<=n;++i){
// cout<<i<<" : "<<pre[i]<<" : "<<val[i]<<endl;
// }
val[rt]=0;
for(reg i=1;i<=n;++i){
ret+=val[i];
if(i==rt) continue;
if(i!=rt&&!pre[i]) return -1;
if(!vis[i]) {
//cout<<" go "<<i<<endl;
top=0;dfs(i);
while(top) in[sta[top--]]=0;
}
}
//cout<<" after dfs "<<cnt<<endl;
for(reg i=1;i<=n;++i) if(!id[i]) id[i]=++cnt;
// for(reg i=1;i<=n;++i) cout<<i<<" -- "<<id[i]<<endl;
if(cnt==n) break;
for(reg i=1;i<=m;++i){
if(id[e[i].x]!=id[e[i].y]){
//cout<<" cut "<<e[i].x<<" "<<e[i].y<<" "<<e[i].v<<endl;
e[i].v-=val[e[i].y];
}
e[i].x=id[e[i].x];
e[i].y=id[e[i].y];
}
//cout<<" endneenndd "<<ret<<" cnt "<<cnt<<endl;
n=cnt;
rt=id[rt];
}
return ret;
}
int main(){
scanf("%d%d%d",&n,&m,&rt);
int lp=0;
int x,y,z;
for(reg i=1;i<=m;++i){
scanf("%d%d%d",&x,&y,&z);
e[++lp].x=x;e[lp].y=y;e[lp].v=z;
}
m=lp;
int ans=wrk(n);
printf("%d",ans);
return 0;
}
}
signed main(){
Miracle::main();
return 0;
}
/*
Author: *Miracle*
Date: 2019/1/7 17:25:32
*/
（一个看似弱智的问题：为什么prim不能用？因为无向图可以用的原因是，两边都可以走。有向图会堵住一边。使得第一次出队不一定最优
尝试这个图：
）
扩展：如果根不定呢？
超级源点，向每个点连接sum(w)+1的边
由于很大，所以最多连一条这样的边
如果最后权值>=sum(w)+sum(w)+1，那么实际上是无解的。
upda：2019.5.6
最小树形图：O(n+mlogn)算法
入边整体-Wmin
从0边不断往上reduce
到根？直接缩链为点
有环？ρ形，边权都是0
先都要上
缩环
所有入边可并堆合并起来，再整体减去Wmin（整体标记）
所有出边用并查集，需要的时候直接定位到这个缩完的点上
每次-Wmin，就是减去入边的最小权值，因为必然会选择恰好一次
最后所有减过的Wmin之和就是ans（因为实际上连接的都是0权边，没有额外贡献）