Description “这一切都是命运石之门的选择。” 试图研制时间机器的机关SERN截获了中二科学家伦太郎发往过去的一条短信，并由此得知了伦太郎制作出了电话微波炉（仮）。 为了掌握时间机器的技术，SERN总部必须尽快将这个消息通过地下秘密通讯网络，传达到所有分部。 SERN共有N个部门（总部编号为0），通讯网络有M条单向通讯线路，每条线路有一个固定的通讯花费Ci。 为了保密，消息的传递只能按照固定的方式进行：从一个已知消息的部门向另一个与它有线路的部门传递（可能存在多条通信线路）。我们定义总费用为所有部门传递消息的费用和。 幸运的是，如果两个部门可以直接或间接地相互传递消息（即能按照上述方法将信息由X传递到Y，同时能由Y传递到X），我们就可以忽略它们之间的花费。 由于资金问题（预算都花在粒子对撞机上了），SERN总部的工程师希望知道，达到目标的最小花费是多少。

Input 多组数据，文件以2个0结尾。 每组数据第一行，一个整数N，表示有N个包括总部的部门（从0开始编号）。然后是一个整数M，表示有M条单向通讯线路。 接下来M行，每行三个整数,Xi,Yi,Ci，表示第i条线路从Xi连向Yi，花费为Ci。 Output 每组数据一行，一个整数表示达到目标的最小花费。

Sample Input 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 Sample Output 150 100 50 【样例解释】 第一组数据：总部把消息传给分部1，分部1再传给分部2.总费用：100+50=150. 第二组数据：总部把消息传给分部1，由于分部1和分部2可以互相传递消息，所以分部1可以无费用把消息传给2.总费用：100+0=100. 第三组数据：总部把消息传给分部1，最小费用为50.总费用：50.

Data Constraint 对于10%的数据，保证M=N-1 对于另30%的数据，N ≤ 20 ，M ≤ 20 对于100%的数据，N ≤ 50000 ，M ≤ 10^5 ，Ci ≤ 10^5 ，数据组数 ≤ 5 数据保证一定可以将信息传递到所有部门。

分析

对于 10%的数据：

又是一个送分点，显然将所有边权相加即为答案。

对于另 30%的数据：

我们枚举保留哪些边，再取一个最小值即可。

时间复杂度：O(2^M)

对于100%的数据：

因为如果两个部门可以直接或间接地相互传递消息，

所以，只要两个点

它们在同一个强连通分量中，

它们的传递费用就可以忽略。

因此，我们可以用tarjan缩点，将一个强连通分量变成一个点。

只要在这个强连通分量中间，

有任意一个点被传递到消息，

那么，这个强连通分量就可以被视为已经收到了消息。

现在问题就变成了，有一些点和一些有向边，选择一些边，使得这些点联通。

很显然，最后的连通图就是一棵树。

再从另一个方面想每一个点一定是有一条边来连接的，

所以最后的答案就是连入每个点的边边权最小的和。

code(c++)

#include <cstdio> #include <algorithm> #include <cstring> #include <string.h> #include <cmath> #include <stdlib.h> #include <math.h> #define ll long long using namespace std; int a[200003],next[200003],b[100003],n,m,x,y,ti,cnt,t,mi; int low[100003],dfn[100003],z[1000003],g[50003],f[50003],ta; int a1[100003][3]; bool bz[100003],bz1[100003]; long long ans; void tarjan(int x) { low[x]=dfn[x]=++ti; bz[x]=bz1[x]=1; z[++ta]=x; for (int i=b[x];i;i=next[i]) { int y=a[i]; if (!bz[y]) { tarjan(y); low[x]=min(low[x],low[y]); } else if (bz1[y]) low[x]=min(low[x],dfn[y]); } if (dfn[x]==low[x]) { cnt++; z[ta+1]=100000000; while (z[ta+1]!=x) { g[z[ta]]=cnt; bz1[z[ta]]=0; ta--; } } } int main() { freopen("1.in","r",stdin); freopen("1.out","w",stdout); while(1) { scanf("%d%d",&n,&m); if((n==0)&&(m==0))return 0; memset(b,0,sizeof(b)); memset(bz,0,sizeof(bz)); memset(bz1,0,sizeof(bz1)); memset(f,57,sizeof(f)); for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&t); a[i]=y; next[i]=b[x]; b[x]=i; a1[i][0]=x; a1[i][1]=y; a1[i][2]=t; } ans=0; ti=ta=cnt=0; tarjan(0); for(int i=1;i<=m;i++) { int q=a1[i][1]; if(g[a1[i][0]]!=g[q])f[g[q]]=min(f[g[q]],a1[i][2]); } for(int i=1;i<=cnt;i++) if(f[i]<=100000000)ans+=f[i]; printf("%lld\n",ans); for(int i=1;i<=n;i++) printf("%d\n",g[i]); } }