畅通工程浙大计算机研究生复试上机考试-2007年

电玩女神 2024-02-18 22:48 7阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td> <h2>畅通工程</h2> Time Limit: 1000/1000 MS (Java/Others)&nbsp;&nbsp;&nbsp;&nbsp;Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 38345&nbsp;&nbsp;&nbsp;&nbsp;Accepted Submission(s): 17093 &nbsp; Problem Description 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。 &nbsp; &nbsp; Input 测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( &lt; 100 )；随后的 N 行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。 &nbsp; &nbsp; Output 对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。 &nbsp; &nbsp; Sample Input <pre>&nbsp;</pre> 3 3 1 2 1 1 3 2 2 3 4 1 3 2 3 2 0 100 &nbsp; &nbsp; Sample Output <pre>&nbsp;</pre> 3 ? &nbsp; &nbsp; Source <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-2007%C4%EA&amp;source=1&amp;searchmode=source" rel="nofollow">浙大计算机研究生复试上机考试-2007年 </a> &nbsp; &nbsp; Recommend lcy&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=1879" rel="nofollow">1879</a>&nbsp;<a href="http://acm.hdu.edu.cn/showproblem.php?pid=1233" rel="nofollow">1233</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=1232" rel="nofollow">1232</a>&nbsp;<a href="http://acm.hdu.edu.cn/showproblem.php?pid=1102" rel="nofollow">1102</a>&nbsp; &nbsp; 今天是图论集训第一天，以前讲数据结构图的时候，对图怕怕的，但怕又能怎样？只有坦然面对，有意思的东西固然难，加油，蓝孩，为了你的Jeep，加油！ &nbsp; #include&lt;iostream&gt; #include&lt;algorithm&gt; #include&lt;string.h&gt; using namespace std; struct kk { &nbsp;&nbsp; &nbsp;int s,e,w; }; int Prim(int N,int M) &nbsp; { &nbsp;&nbsp; &nbsp;kk a[10000]; &nbsp;&nbsp; &nbsp;int i,j,pos=1,min,flag=0,result=0,map[101][101],low[101],visit[101]; &nbsp; &nbsp; low数组存当前到各个顶点的最小权值 &nbsp;&nbsp; &nbsp;memset(map,0x3f3f3f3f,sizeof(map)); &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 将邻接矩阵设为无穷大 &nbsp;&nbsp; &nbsp;memset(visit,0,sizeof(visit)); &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;for(i=0;i&lt;N;i++) &nbsp;&nbsp; &nbsp;{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;scanf("%d%d%d",&amp;a[i].s,&amp;a[i].e,&amp;a[i].w); &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;map[a[i].s][a[i].e]=a[i].w; &nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;map[a[i].e][a[i].s]=a[i].w; &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;visit[pos]=1; &nbsp;&nbsp; &nbsp;for(i=1;i&lt;=M;i++) &nbsp;&nbsp; &nbsp;{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(!visit[i]) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;low[i]=map[pos][i]; &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;for(i=0;i&lt;M-1;i++) &nbsp;&nbsp; &nbsp;{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;min=0x3f3f3f3f; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;for(j=1;j&lt;=M;j++) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(!visit[j]&amp;&amp;low[j]&lt;min) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;min=low[j]; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;pos=j; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;result+=min; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;visit[pos]=1; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;for(j=1;j&lt;=M;j++) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(!visit[j]&amp;&amp;low[j]&gt;map[pos][j]) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;low[j]=map[pos][j]; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;for(i=1;i&lt;=M;i++) &nbsp;&nbsp; &nbsp;{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(visit[i]==0) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;flag=1; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;break; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;if(flag==1) &nbsp;&nbsp; &nbsp;return 0; &nbsp;&nbsp; &nbsp;else &nbsp;&nbsp; &nbsp;return result; } int main() { &nbsp;&nbsp; &nbsp;int n,m; &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;while(~scanf("%d%d",&amp;n,&amp;m)) &nbsp;&nbsp; &nbsp;{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(n==0) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;break; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;int t=Prim(n,m); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(t==0) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;cout&lt;&lt;"?"&lt;&lt;endl; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;else &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;cout&lt;&lt;t&lt;&lt;endl; &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;return 0; } &nbsp; &nbsp; </td> 
 </tr> 
 </tbody> 
</table>