题目描述

“这一切都是命运石之门的选择。” 

试图研制时间机器的机关SERN截获了中二科学家伦太郎发往过去的一条短 信，并由此得知了伦太郎制作出了电话微波炉（仮）。

 为了掌握时间机器的技术，SERN总部必须尽快将这个消息通过地下秘密通讯 网络，传达到所有分部。

 SERN共有N个部门（总部编号为0），通讯网络有M条单向通讯线路，每条线 路有一个固定的通讯花费Ci。 

为了保密，消息的传递只能按照固定的方式进行：从一个已知消息的部门向 另一个与它有线路的部门传递（可能存在多条通信线路）。我们定义总费用为所 有部门传递消息的费用和。

 幸运的是，如果两个部门可以直接或间接地相互传递消息（即能按照上述方 法将信息由X传递到Y，同时能由Y传递到X），我们就可以忽略它们之间的花费。 

由于资金问题（预算都花在粒子对撞机上了），SERN总部的工程师希望知道， 达到目标的最小花费是多少。

输入

多组数据，文件以2个0结尾。 

每组数据第一行，一个整数N，表示有N个包括总部的部门（从0开始编号）。 然后是一个整数M，表示有M条单向通讯线路。

接下来M行，每行三个整数,Xi,Yi,Ci，表示第i条线路从Xi连向Yi，花费为 Ci。

输出

每组数据一行，一个整数表示达到目标的最小花费。

样例输入

3 3

0 1 100

1 2 50

0 2 100

3 3

0 1 100

1 2 50

2 1 100

2 2

0 1 50

0 1 100

0 0

样例输出

150

100

50

提示

【样例解释】 

第一组数据：总部把消息传给分部1，分部1再传给分部2.总费用：100+50=150.

 第二组数据：总部把消息传给分部1，由于分部1和分部2可以互相传递消息，所以分部1可以无费用把消息传给2.总费用：100+0=100. 

第三组数据：总部把消息传给分部1，最小费用为50.总费用：50.

 【数据范围】 

对于10%的数据，保证M=N-1

对于另30%的数据，N ≤ 20 ，M ≤ 20 

对于100%的数据，N ≤ 50000 ，M ≤ 10^5 ，Ci ≤ 10^5 ，

数据组数 ≤ 5 ，数据保证一定可以将信息传递到所有部门。

考试思路历程

考试的时候就觉得这是道水题，因为很明显的tarjan求强联通分量缩点，然后思路有点乱，想过一个个枚举边然后找min值（这就是正解），但觉得这种做法太傻逼，也就没打，又去看了一遍题面，发现有这么一句话“传达到所有分部”，然后就觉得是要经过所有点，就自然而然的想到了kruscal求最小生成树，但我忽略了最小生成树只是针对于无向图而言的，并不适用于有向图，qj测试点还没输出换行然后就爆零滚粗了。

题解

其实这题确实水，tarjan缩完点后就枚举每一个点然后找权值最小的入边就可以了，只要建个反图就很好处理。

其实是个贪心的思想，至于正确性的话，就是因为题目中保证都能到达，所以找最小入边的正确性也就很显然了，也可以自己话个图理解一下。

最后，对于多测题，数组不清空，爆零两行泪。

收获

还是基础知识不牢固，都不知道kruscal只适用于无向图，以后一定要多注意算法的适用范围这种东西，不然很容易爆零的。

 

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 const int N=5e5+10; 9 int n,m,num,top;10 int tot,first[N],nex[N],edge[N],to[N],s[N],in[N],c[N],cnt,low[N],dfn[N];11 inline int read(){12 int ss=0;char bb=getchar();13 while(bb<48||bb>57)bb=getchar();14 while(bb>=48&&bb<=57)ss=(ss<<1)+(ss<<3)+(bb^48),bb=getchar();15 return ss;16 }17 void add(int a,int b,int ci){18 to[++tot]=b,edge[tot]=ci,nex[tot]=first[a],first[a]=tot;19 }20 int totc,firstc[N],toc[N],nexc[N],edgec[N];21 void add_c(int a,int b,int ci){22 toc[++totc]=b,edgec[totc]=ci,nexc[totc]=firstc[a],firstc[a]=totc;23 }24 void init(){25 tot=0;26 memset(first,0,sizeof(first));27 memset(nex,0,sizeof(nex));28 memset(to,0,sizeof(to));29 memset(s,0,sizeof(s));30 memset(in,0,sizeof(in));31 memset(dfn,0,sizeof(dfn));32 memset(low,0,sizeof(low));33 memset(c,0,sizeof(c));34 memset(firstc,0,sizeof(firstc));35 memset(nexc,0,sizeof(nexc));36 memset(toc,0,sizeof(toc));37 memset(edgec,0,sizeof(edgec));38 top=0,totc=0,cnt=0;39 }40 void tarjan(int x){41 dfn[x]=low[x]=++num;s[++top]=x,in[x]=1;42 for(int i=first[x];i;i=nex[i]){43 int y=to[i];44 if(!dfn[y]){45 tarjan(y);46 low[x]=min(low[y],low[x]);47 }48 else if(in[y]){49 low[x]=min(low[x],dfn[y]);50 }51 }52 if(dfn[x]==low[x]){53 cnt++;int y;54 do{55 y=s[top--],in[y]=0;56 c[y]=cnt;57 }while(x!=y);58 }59 }60 int main(){61 for(;;){62 n=read();m=read();63 if(n==0&&m==0) break;64 int pf=0;65 init();66 for(int i=1;i<=m;i++){67 int a,b,ci;68 a=read(),b=read(),ci=read();69 a++,b++;pf+=ci;70 add(a,b,ci);71 }72 if(m==n-1){73 printf("%d\n",pf);74 continue;75 }76 for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);77 for(int x=1;x<=n;x++){78 for(int i=first[x];i;i=nex[i]){79 int y=to[i];80 if(c[x]==c[y]) continue;81 //cout<
            
             <<" "<
             
              <<" "<
              
               <