最小树形图

题目描述

这是一道模板题。

给定包含 n 个结点， m 条有向边的一个图。试求一棵以结点 r 为根的最小树形图，并输出最小树形图每条边的权值之和，如果没有以 r为根的最小树形图，输出 −1。

输入格式

第一行包含三个整数 n,m,r，意义同题目所述。

接下来 mm 行，每行包含三个整数 u,v,w表示图中存在一条从 u 指向 v 的权值为 w 的有向边。

输出格式

如果原图中存在以 r 为根的最小树形图，就输出最小树形图每条边的权值之和，否则输出 -1。

样例

样例输入1

4 6 11 2 31 3 14 1 24 2 23 2 13 4 1

样例输出 1

3

样例解释 1

最小树形图中包含第 2， 5， 6 三条边，总权值为 1 + 1 + 1 = 3

样例输入 2

4 6 31 2 31 3 14 1 24 2 23 2 13 4 1

样例输出 2

4

样例输出 2

最小树形图中包含第 3， 5， 6 三条边，总权值为 2 + 1 + 1 =4

样例输入 3

4 6 21 2 31 3 14 1 24 2 23 2 13 4 1

样例输出 3

-1

样例解释 3

无法构成最小树形图，故输出 -1 。

 

 

模板题 

下标从0开始

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 const int INF=0x3f3f3f3f; 6 #define MAXN 400005 7 #define MAXM 400010 8 using namespace std; 9 struct Edge{10     int u,v;11     int cost;12 }edge[MAXM];13 14 int pre[MAXN],id[MAXN],visit[MAXN];15 int in[MAXN];16 17 int zhuliu(int root,int n,int m){18     int res=0;19     while(1){20         for(int i=0;i
          
           >n>>m>>r;80     for(int i=0;i
           
            >edge[i].u>>edge[i].v>>edge[i].cost;82 edge[i].u--;83 edge[i].v--;84 }85 int ans=zhuliu(r-1,n,m);86 cout<
            
             <
            
           
          
         
        
       
      

 

 

下标从1开始（要改两个地方：1.tn  2.--m -> m--）

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 const int INF=0x3f3f3f3f; 6 #define MAXN 400005 7 #define MAXM 400010 8 using namespace std; 9 struct Edge{10     int u,v;11     int cost;12 }edge[MAXM];13 14 int pre[MAXN],id[MAXN],visit[MAXN];15 int in[MAXN];16 17 int zhuliu(int root,int n,int m){18     int res=0;19     while(1){20         for(int i=1;i<=n;i++){21             in[i]=INF;22         }23         for(int i=1;i<=m;i++){24             if(edge[i].u!=edge[i].v&&edge[i].cost
          
           >n>>m>>r;80     for(int i=1;i<=m;i++){81         cin>>edge[i].u>>edge[i].v>>edge[i].cost;82     }83     int ans=zhuliu(r,n,m);84     cout<
           
            <