学步园

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

解题思路：这道题给出的数据里有一些路是已经建好的，所以这条路的成本就不计入总成本中，所以把它直接设置为0。这道题要注意的就是这个了，然后又是prim算法，我晕哦，畅通工程怎么都这个算法。

#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,N,status,weight;<br /> while (scanf("%d",&NumOfVillage)!=EOF&&NumOfVillage)<br /> {<br /> N = (NumOfVillage*(NumOfVillage-1))/2;<br /> for (i=1;i<=NumOfVillage;i++)<br /> {<br /> for (j=1;j<=NumOfVillage;j++)<br /> {<br /> if(i==j)<br /> Graph[i][j] = 0;<br /> else<br /> Graph[i][j] = INIT;<br /> }<br /> }<br /> while (N--)<br /> {<br /> scanf("%d%d%d%d",&i,&j,&weight,&status);<br /> if(!status)<br /> {<br /> Graph[i][j] = weight;<br /> Graph[j][i] = weight;<br /> }<br /> else<br /> {<br /> Graph[i][j] = 0;<br /> Graph[j][i] = 0;<br /> }<br /> }<br /> Prim();<br /> printf("%ld/n",sum);<br /> }<br /> return 0;<br /> }