JZOJ.4686. 【NOIP2016提高A组8.12】通讯

Problem

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

Data Constraint

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

Hint

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

Solution

10分做法： 这10分是送的，直接所有边的和就是答案。 100分做法： 如果有两个部门可以直接或间接地相互传递消息，那么就忽略他们之间传送所花费的值。所以我们可以想到将强连通分量中的所有点合并成一个点，然后再求每一个强连通分量的入边的最小值，将它统计到答案。 ——注意：数组初始化要非常地小心，不要因为小小的不注意坑了很多时间！

Code

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #define M 100010 #define N 50010 #define LL long long #define fo(i,a,b) for(i=a;i<=b;i++) using namespace std; LL v[M],z,ans,a[M][3],b[N]; int i,j,k,n,m,x,y,tot,top,h,cnt; int g[N],go[M],next[M],head[M],st[N],low[N],dfn[N]; bool bz[N]; void lb(int x,int y,LL z) { go[++tot]=y; next[tot]=head[x]; head[x]=tot; v[tot]=z; } void tarjan(int x) { h++; dfn[x]=low[x]=h; bz[x]=1; st[++top]=x; int i,now; for (i=head[x];i;i=next[i]) { now=go[i]; if (dfn[now]==-1) { tarjan(now); low[x]=min(low[x],low[now]); } else if (bz[now]) low[x]=min(low[x],dfn[now]); } if (dfn[x]==low[x]) { cnt++; while (st[top+1]!=x) { bz[st[top]]=0; g[st[top]]=cnt; top--; } } } void qsort(int l,int r) { int i=l,j=r; LL mid=a[(l+r)/2][2]; while (i<j) { while (a[i][2]<mid) i++; while (a[j][2]>mid) j--; if (i<=j) { swap(a[i],a[j]); i++; j--; } } if (l<j) qsort(l,j); if (i<r) qsort(i,r); } int main() { while (1) { scanf("%d%d",&n,&m); if (n==0 && m==0) break; memset(go,0,sizeof(go)); memset(next,0,sizeof(next)); memset(head,0,sizeof(head)); memset(g,0,sizeof(g)); memset(low,0,sizeof(low)); memset(st,0,sizeof(st)); memset(dfn,255,sizeof(dfn)); memset(bz,0,sizeof(bz)); memset(b,127,sizeof(b)); cnt=tot=top=h=0; fo(i,1,m) { scanf("%d%d%lld",&x,&y,&z); lb(x,y,z); a[i][0]=x; a[i][1]=y; a[i][2]=z; } tarjan(0); qsort(1,m); fo(i,0,n-1) { for(j=head[i];j;j=next[j]) { int now=go[j]; if (g[i]!=g[now]) b[g[now]]=min(b[g[now]],v[j]); } } ans=0; fo(i,1,cnt-1) ans+=b[i]; printf("%lld\n",ans); } }

——2016.8.12