学步园

http://acm.hdu.edu.cn/showproblem.php?pid=1102

题目大意：又是求最短路径的问题啦，只不过有些路已经建好了，现在要你计算连通所有点，还要花修路费，建好的就不用考虑了。

解题思路：已经做到麻木的类型题了，不说了。

#include <stdio.h><br /> #include <string.h><br /> #define MaxSize 105<br /> #define INIT 999999999</p> <p>int Graph[MaxSize][MaxSize];<br /> long sum;<br /> bool visited[MaxSize];</p> <p>int NumOfVillage;</p> <p>void Prim()<br /> {<br /> int i,j;<br /> sum = 0;<br /> int dist[MaxSize];<br /> int min,locate;<br /> memset(visited,0,sizeof(visited));<br /> for(i=1;i<=NumOfVillage;i++)<br /> dist[i] = Graph[1][i];<br /> visited[1] = true;<br /> for (j=1;j<=NumOfVillage;j++)<br /> {<br /> min = INIT;<br /> for (i=1;i<=NumOfVillage;i++)<br /> {<br /> if(!visited[i]&&dist[i]<min)<br /> {<br /> min = dist[i];<br /> locate = i;<br /> }<br /> }<br /> visited[locate] = true;<br /> for (i=1;i<=NumOfVillage;i++)<br /> {<br /> if (!visited[i]&&dist[i]>Graph[locate][i])<br /> {<br /> dist[i] = Graph[locate][i];<br /> }<br /> }</p> <p> }<br /> for (i=1;i<=NumOfVillage;i++)<br /> {<br /> sum+=dist[i];<br /> }<br /> }</p> <p>int main()<br /> {<br /> int i,j,Q;<br /> while (scanf("%d",&NumOfVillage)!=EOF)<br /> {<br /> for (i=1;i<=NumOfVillage;i++)<br /> {<br /> for(j=1;j<=NumOfVillage;j++)<br /> scanf("%d",&Graph[i][j]);<br /> }<br /> scanf("%d",&Q);<br /> while (Q--)<br /> {<br /> scanf("%d%d",&i,&j);<br /> Graph[i][j] = 0;<br /> Graph[j][i] = 0;<br /> }<br /> Prim();<br /> printf("%ld/n",sum);<br /> }<br /> return 0;<br /> }