1822: 布线问题 Prim

阳光穿透心脏的1/2处 2024-02-19 19:46 9阅读 0赞

### 1822: 布线问题 ###

时间限制: 1 Sec 内存限制: 64 MB  
提交: 99 解决: 32  
您该题的状态：**已完成**  
\[[提交][Link 1]\]\[[状态][Link 2]\]\[[讨论版][Link 3]\]

### 题目描述 ###

南阳理工学院要进行用电线路改造，现在校长要求设计师设计出一种布线方式，该布线方式需要满足以下条件：  
1、把所有的楼都供上电。  
2、所用电线花费最少

### 输入 ###

第一行是一个整数n表示有n组测试数据。(n<5)  
每组测试数据的第一行是两个整数v,e.  
v表示学校里楼的总个数(v<=500)  
随后的e行里，每行有三个整数a,b,c表示a与b之间如果建铺设线路花费为c(c<=100)。（哪两栋楼间如果没有指明花费，则表示这两栋楼直接连通需要费用太大或者不可能连通）  
随后的1行里，有v个整数,其中第i个数表示从第i号楼接线到外界供电设施所需要的费用。( 0<e<v\*(v-1)/2 )  
（楼的编号从1开始），由于安全问题，只能选择一个楼连接到外界供电设备。  
数据保证至少存在一种方案满足要求。

### 输出 ###

每组测试数据输出一个正整数,表示铺设满足校长要求的线路的最小花费。

### 样例输入 ###

### 样例输出 ###

### 提示 ###

nyoj38

### 来源 ###

[nyoj图论][nyoj]

<table> 
 <tbody> 
  <tr> 
   <td><span style="color:#000000;"><strong>题目智能推荐</strong><br><br><a href="http://xyoj.xynu.edu.cn/problem.php?id=1345" rel="nofollow">1345</a>&nbsp;<a href="http://xyoj.xynu.edu.cn/problem.php?id=1308" rel="nofollow">1308</a>&nbsp;<a href="http://xyoj.xynu.edu.cn/problem.php?id=2389" rel="nofollow">2389</a>&nbsp;<a href="http://xyoj.xynu.edu.cn/problem.php?id=1872" rel="nofollow">1872</a>&nbsp;<a href="http://xyoj.xynu.edu.cn/problem.php?id=1384" rel="nofollow">1384</a>&nbsp;<a href="http://xyoj.xynu.edu.cn/problem.php?id=1302" rel="nofollow">1302</a>&nbsp;</span></td> 
  </tr> 
 </tbody> 
</table>

水题，加油，相信自己

#include<iostream>
    #include<cstdio>
    #include<cstring> 
    using namespace std;
    #define range 502
    #define inf 0x7fffffff
    int map[range][range];
    int dis[range];
    bool vis[range];
    int a,b;
    int  prim()
    {
    	int i,j,sum=0;
    	int pos=0;
    	for(i=0;i<a;i++)
    	dis[i]=map[pos][i];
    	vis[pos]=true;
    	for(i=0;i<a-1;i++)
    	{
    		int min=inf;
    		for(j=0;j<a;j++)
    		{
    			if(!vis[j]&&dis[j]<min&&dis[j]!=0)
    			{
    				min=dis[j];
    				pos=j;
    			}
    		}
    		
    		sum+=min;
    		vis[pos]=true;
    		for(j=0;j<a;j++)
    		{
    			if(!vis[j]&&dis[j]>map[pos][j])
    			dis[j]=map[pos][j];
    		}
    	}
    	
    	return sum;
    }
    int main()
    {
    	int n,i,j;
    	int d1,d2,dd;
    	cin>>n;
    	while(n--)
    	{
    		int min=inf;
    		
    		memset(vis,false,sizeof(vis));
    		memset(dis,inf,sizeof(dis));
    		cin>>a>>b;
    		for(i=0;i<a;i++)
    		{
    			for(j=i;j<a;j++)
    			map[i][j]=map[j][i]=inf;
    		 } 
    //		 for(i=0;i<a;i++)
    //		 {
    //		 	for(j=0;j<a;j++)
    //			 {
    //			 	printf("%d ",map[i][j]);
    //			 }
    //			 printf("\n"); 
    //		 }
    		 
    		for(i=0;i<b;i++)
    		{
    			cin>>d1>>d2>>dd;
    			map[d1-1][d2-1]=map[d2-1][d1-1]=dd;
    		}
    		
    		for(i=0;i<a;i++)
    		{
    			cin>>dd;
    			if(dd<min)
    			min=dd;
    		}
    		
    		cout<<prim()+min<<endl;
    	}
    	return 0;
    }

另外，要注意，对数组初始化，用memset只能赋0，或-1.

而fill可以赋任何值。用法

int a[200];
    fill(a, a+100, 1);

[Link 1]: http://xyoj.xynu.edu.cn/submitpage.php?id=1822
[Link 2]: http://xyoj.xynu.edu.cn/problemstatus.php?id=1822
[Link 3]: http://xyoj.xynu.edu.cn/bbs.php?pid=1822
[nyoj]: http://xyoj.xynu.edu.cn/problemset.php?search=nyoj%E5%9B%BE%E8%AE%BA