问题 B: 通讯

时间限制: 1 Sec  内存限制: 256 MB

题目描述

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

试图研制时间机器的机关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 30 1 1001 2 500 2 1003 30 1 1001 2 502 1 1002 20 1 500 1 1000 0

样例输出

15010050

提示

【样例解释】 

第一组数据：总部把消息传给分部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

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

　　这道题当时考试被我选择优先解决，毕竟怎么打还是比较明了的。

　　首先由于可以互相到达的两个部门费用为0，tarjan一遍肯定没跑了。然后我们注意到花费与走这条路径的次数无关，换句话说，一个特殊的最小生成树。

　　为什么说他特殊呢？因为每一条边都是单向边，我们必须让每一条边都从父亲指向儿子，复杂度为m的克鲁斯卡尔虽然快但是貌似无法满足这条性质，因此当时打算打prim，然而prim n^2的复杂度真心感人，但我们可以知道我们每一次找的是离树最近的点，我们只要知道合法最小值就行了，于是乎默默的打了一个n*log n的线段树优化prim，A了……（还真是不卡我常数啊）。不过考完之后再仔细去想一下dfs+贪心就好了嘛……白白加了一个log n……

　　

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 #include
           
              6 #include
            
              7 #include
             
               8 #define N 50005 9 #define M 100005 10 using namespace std; 11 int n,m,zz1,a[N],b[N],zz2; 12 struct ro{ 13 int from,to; 14 int next,l; 15 }road[M],road2[M]; 16 void build2(int x,int y,int z){ 17 zz2++; 18 road2[zz2].to=y; 19 road2[zz2].from=x; 20 road2[zz2].l=z; 21 road2[zz2].next=b[x]; 22 b[x]=zz2; 23 } 24 long long sum; 25 bool rz[N],rz2[N]; 26 int dfn[N],low[N],zz3,st[N],top,zz4,belong[N]; 27 void tar(int x) 28 { 29 zz3++; 30 dfn[x]=low[x]=zz3; 31 rz[x]=rz2[x]=1; 32 top++; 33 st[top]=x; 34 for(int i=b[x];i>0;i=road2[i].next) 35 { 36 int y=road2[i].to; 37 if(!rz2[y]) 38 { 39 tar(y); 40 low[x]=min(low[x],low[y]); 41 } 42 else if(rz[y]) 43 { 44 low[x]=min(low[x],dfn[y]); 45 } 46 } 47 if(low[x]==dfn[x]) 48 { 49 int v; 50 zz4++; 51 do{ 52 v=st[top]; 53 top--; 54 rz[v]=0; 55 belong[v]=zz4; 56 }while(dfn[v]!=low[v]); 57 } 58 } 59 void build(int x,int y,int z){ 60 zz1++; 61 road[zz1].to=y; 62 road[zz1].from=x; 63 road[zz1].l=z; 64 road[zz1].next=a[x]; 65 a[x]=zz1; 66 } 67 struct no{ 68 int left,right; 69 int mn,mid; 70 }node[N*4]; 71 int mn[N],pre[N]; 72 void bui(int left,int right,int x){ 73 node[x].left=left; 74 node[x].right=right; 75 if(left==right) 76 { 77 node[x].mn=mn[0]; 78 return; 79 } 80 int mid=(left+right)/2; 81 node[x].mid=mid; 82 bui(left,mid,2*x); 83 bui(mid+1,right,2*x+1); 84 node[x].mn=min(node[2*x].mn,node[2*x+1].mn); 85 } 86 void change(int left,int right,int x,int z){ 87 if(node[x].left==node[x].right) 88 { 89 node[x].mn=z; 90 return; 91 } 92 int mid=node[x].mid; 93 if(left>mid)change(left,right,2*x+1,z); 94 else change(left,right,2*x,z); 95 node[x].mn=min(node[x*2].mn,node[2*x+1].mn); 96 } 97 int get(int x){ 98 if(node[x].left==node[x].right) 99 return node[x].left;100 if(node[x*2].mn>node[2*x+1].mn) return get(2*x+1);101 else return get(2*x);102 }103 bool fl[N];104 int main(){105 while(~scanf("%d%d",&n,&m)){106 if(n==m&&n==0)break;107 zz2=zz1=zz3=zz4=0;108 top=0;109 memset(fl,0,sizeof(fl));110 memset(pre,0,sizeof(pre));111 memset(mn,0x7f,sizeof(mn));112 memset(belong,0,sizeof(belong));113 memset(rz,0,sizeof(rz));114 memset(rz2,0,sizeof(rz2));115 memset(a,0,sizeof(a));116 memset(b,0,sizeof(b));117 sum=0;118 for(int i=1;i<=m;i++)119 {120 int x,y,z;121 scanf("%d%d%d",&x,&y,&z);122 build2(x,y,z);123 if(m==n-1)sum+=z;124 }125 if(m==n-1)126 {127 printf("%lld\n",sum);128 continue;129 }130 for(int i=0;i
              
               0;j=road2[j].next)137 {138 int y=road2[j].to;139 if(belong[i]!=belong[y])140 {141 build(belong[i],belong[y],road2[j].l);142 }143 }144 }145 bui(1,zz4,1);146 mn[belong[0]]=0;147 for(int i=1;i<=zz4;i++)148 {149 int bj=belong[0];150 if(i!=1)151 {152 bj=get(1);153 }154 fl[bj]=1;155 change(bj,bj,1,mn[0]);156 for(int j=a[bj];j>0;j=road[j].next)157 {158 int y=road[j].to;159 if(mn[y]>road[j].l)160 {161 pre[y]=j;162 mn[y]=road[j].l;163 if(!fl[y])164 {165 change(y,y,1,mn[y]);166 }167 }168 }169 }170 for(int i=1;i<=zz4;i++)171 {172 if(i==belong[0]) continue;173 sum+=road[pre[i]].l;174 }175 printf("%lld\n",sum);176 }177 return 0;178 }
              
             
            
           
          
         
        
       

　　其实个人对当时对于这道题的表现并不满意，按代码量来说我不到半个小时就可以了，但是很奇怪的是对于我一直倒背如流的线段树竟然出了好多低级失误，实属不该（这可能是这次打的一般的主要原因）。