本文共 3432 字，大约阅读时间需要 11 分钟。

题意：输出一个有向图的最小生成树。

题解：朱刘算法

1.有向图的最小生成树是最小树形图。解释为什么不能用prim解决这个问题。

有四条边:1->2权值为8、1->3权值为8、2->3权值为4、3->2权值为3。

prim选择两条边：1->2权值为8、2->3权值为4。该最小树形图权值为12。

正解为：1->3权值为8、3->2权值为3。该最小树形图权值为11。

因为有环的存在导致有向图和无向图不同。

2.朱刘算法求解最小树形图，参考模板：

/* 最小树形图 朱刘算法模板 时间复杂度O(nm) 数据为int型 */  #include 
   
      #include 
    
      #include
     
       #include 
      
         #define MAXN 101  #define MAXM 10000+10  #define INF 0x3f3f3f3f  using namespace std;  struct Node{	double x , y ;} ;Node node[MAXN] ;struct Edge  {      int from, to ;	double cost;  };  Edge edge[MAXM];  int pre[MAXN];//存储父节点  int vis[MAXN];//标记作用  int id[MAXN];//id[i]记录节点i所在环的编号  double in[MAXN];//in[i]记录i入边中最小的权值  double zhuliu(int root, int n, int m, Edge *edge)//root根 n点数 m边数  {      double res = 0 ;	int u , v ;      while(1)      {          for(int i = 1 ; i <= n; i++)              in[i] = INF;//初始化          for(int i = 0 ; i < m; i++)          {              Edge E = edge[i];              if(E.from != E.to && E.cost < in[E.to])              {                  pre[E.to] = E.from;//记录前驱                  in[E.to] = E.cost;//更新              }          }          for(int i = 1 ; i <= n; i++)              if(i != root && in[i] == INF)                  return -1;//有其他孤立点 则不存在最小树形图          //找有向环          int tn = 0 ;//记录当前查找中 环的总数          memset(id, -1, sizeof(id));          memset(vis, -1, sizeof(vis));          in[root] = 0;//根          for(int i = 1 ; i <= n; i++)          {              res += in[i];//累加              v = i;              //找图中的有向环 三种情况会终止while循环              //1,直到出现带有同样标记的点说明成环              //2,节点已经属于其他环              //3,遍历到根              while(vis[v] != i && id[v] == -1 && v != root)              {                  vis[v] = i;//标记                  v = pre[v];//一直向上找              }              //因为找到某节点属于其他环  或者 遍历到根  说明当前没有找到有向环              if(v != root && id[v] == -1)//必须上述查找已经找到有向环              {                  tn++ ;                for(int u = pre[v]; u != v; u = pre[u])                      id[u] = tn;//记录节点所属的 环编号                  id[v] = tn ;//记录节点所属的 环编号  环编号累加              }          }          if(tn == 0) break;//不存在有向环          //可能存在独立点          for(int i = 1 ; i <= n; i++)              if(id[i] == -1)                  id[i] = ++tn ;//环数累加          //对有向环缩点  和SCC缩点很像吧          for(int i = 0; i < m; i++)          {              v = edge[i].to;              edge[i].from = id[edge[i].from];              edge[i].to = id[edge[i].to];              //
       
        有向边               //两点不在同一个环 u到v的距离为 边权cost - in[v]              if(edge[i].from != edge[i].to)                  edge[i].cost -= in[v];//更新边权值 继续下一条边的判定          }          n = tn;//以环总数为下次操作的点数 继续执行上述操作 直到没有环          root = id[root];      }      return res;  }  int main()  {      int n , m ;//N个点 M条有向边      int i , j ;	while(scanf("%d%d", &n, &m) != EOF)      {  	        for(i = 1 ; i <= n ; i ++)            scanf("%lf%lf" , &node[i].x , &node[i].y) ;        for(i = 0 ; i < m ; i ++)        {          scanf("%d%d" , &edge[i].from , &edge[i].to) ;		  edge[i].cost = sqrt((node[edge[i].from].x - node[edge[i].to].x) * (node[edge[i].from].x - node[edge[i].to].x) + (node[edge[i].from].y - node[edge[i].to].y) * (node[edge[i].from].y - node[edge[i].to].y)) ;			}        double ans = zhuliu(1 , n , m , edge);          if(ans == -1)              printf("poor snoopy\n"); //不存在          else              printf("%.2f\n" , ans);     }      return 0;  }