HDU1233 还是畅通工程

末蓝、 2022-05-28 00:53 162阅读 0赞

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div> 
     <span style="margin-right:20px;"></span> 
    </div></td> 
  </tr> 
  <tr> 
   <td align="center"><h1 style="color:#1a5cc8;">还是畅通工程</h1><strong><span style="font-size:12px;font-family:Arial;color:#008000;">Time Limit: 4000/2000 MS (Java/Others)&nbsp;&nbsp;&nbsp;&nbsp;Memory Limit: 65536/32768 K (Java/Others)<br>Total Submission(s): 53787&nbsp;&nbsp;&nbsp;&nbsp;Accepted Submission(s): 24423<br></span></strong><br><br> 
    <div>
      Problem Description 
    </div> 
    <div>
      某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。 
     <br> 
    </div> 
    <div>
      &nbsp; 
    </div><br> 
    <div>
      Input 
    </div> 
    <div>
      测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( &lt; 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 
     <br>当N为0时，输入结束，该用例不被处理。 
     <br> 
    </div> 
    <div>
      &nbsp; 
    </div><br> 
    <div>
      Output 
    </div> 
    <div>
      对每个测试用例，在1行里输出最小的公路总长度。 
     <br> 
    </div> 
    <div>
      &nbsp; 
    </div><br> 
    <div>
      Sample Input 
    </div> 
    <div> 
     <pre></pre> 
     <div style="font-family:'Courier New', Courier, monospace;">
       31 2 11 3 22 3 441 2 11 3 41 4 12 3 32 4 23 4 50 
     </div> 
    </div> 
    <div>
      &nbsp; 
    </div> 
    <div>
      Sample Output 
    </div> 
    <div> 
     <pre></pre> 
     <div style="font-family:'Courier New', Courier, monospace;">
       35 
      <div style="font-size:14px;border-top:#b7cbff 1px dashed;font-family:'Times New Roman';border-right:#b7cbff 1px dashed;border-bottom:#b7cbff 1px dashed;padding-bottom:6px;padding-top:6px;padding-left:6px;border-left:#b7cbff 1px dashed;padding-right:6px;background-color:#f4fbff;"> 
       <div style="font-family:Arial;border-bottom:#b7cbff 1px dashed;font-weight:bold;color:#7ca9ed;"> 
        <em>Hint</em> 
       </div>Hint 
      </div> 
      <span style="font-size:1px;"> </span>Huge input, scanf is recommended. 
     </div> 
    </div> 
    <div>
      &nbsp; 
    </div><br> 
    <div>
      Source 
    </div> 
    <div> 
     <a href="http://acm.hdu.edu.cn/search.php?field=problem&amp;key=%D5%E3%B4%F3%BC%C6%CB%E3%BB%FA%D1%D0%BE%BF%C9%FA%B8%B4%CA%D4%C9%CF%BB%FA%BF%BC%CA%D4-2006%C4%EA&amp;source=1&amp;searchmode=source" rel="nofollow">浙大计算机研究生复试上机考试-2006年 </a> 
    </div> 
    <div>
      &nbsp; 
    </div><br> 
    <div>
      Recommend 
    </div> 
    <div>
      JGShining&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;We have carefully selected several similar problems for you:&nbsp;&nbsp; 
     <a href="http://acm.hdu.edu.cn/showproblem.php?pid=1102" rel="nofollow">1102</a>&nbsp; 
     <a href="http://acm.hdu.edu.cn/showproblem.php?pid=1875" rel="nofollow">1875</a>&nbsp; 
     <a href="http://acm.hdu.edu.cn/showproblem.php?pid=1879" rel="nofollow">1879</a>&nbsp; 
     <a href="http://acm.hdu.edu.cn/showproblem.php?pid=1301" rel="nofollow">1301</a>&nbsp; 
     <a href="http://acm.hdu.edu.cn/showproblem.php?pid=1162" rel="nofollow">1162</a>&nbsp; 
    </div></td> 
  </tr> 
 </tbody> 
</table>

//最短路的学习
    //克鲁斯卡尔(Kruskal) 
    /*
    
    1.需要对路径进行储存，这里用的是不定数组vector 
    2.需要对路径进行升序排列
    3.将村庄并起来
    4.将路的权值加起来，知道所有的村庄都连接在一起(在循环的时候，为了优化一下程序，需要判断一下，全部连起来之后就跳出循环) 
    
    */
    
    
    #include<cstdio> 
    #include<algorithm>
    #include<vector>
    using namespace std;
    struct Road{int x,y,cost;}w;
    vector<Road> d;
    bool cmp(Road x,Road y)
    {
    	return x.cost<y.cost;
    }
    int pre[109];
    void init(int n)
    {
    	for(int i=1;i<=n;i++)	pre[i]=i;
    }
    int find(int x)
    {
    	return x==pre[x]?x:pre[x]=find(pre[x]);
    }
    bool join(int x,int y)	//返回一个bool类型的数，表示是否合并 
    {
    	x=find(x);
    	y=find(y);
    	if(x!=y)
    	{
    		pre[x]=y;
    		return true;
    	}
    	return false; 
    }
    
    int main()
    {
    	int n;
    	while(~scanf("%d",&n)&&n)
    	{
    		int m=n*(n-1)/2;
    		d.clear();
    		init(n);
    		for(int i=0;i<m;i++)
    		{
    			scanf("%d %d %d",&w.x,&w.y,&w.cost);
    			d.push_back(w);
    		}
    		sort(d.begin(),d.end(),cmp);
    		int sum=0;				//花费 
    		int cnt=0;				//已经完成的条数 
    		for(int i=0;i<d.size();i++)
    		{
    			if(join(d[i].x,d[i].y))
    			{
    				cnt++;				//表示又合并两个城镇 
    				sum+=d[i].cost;		//
    			}
    			if(cnt==n-1)			//小优化，某些题需要s 
    				break;
    		}
    		printf("%d\n",sum);
    	}
    	return 0;
    }