poj 2421
<div class="postcontent"><div id="cnblogs_post_body"> 题目大意是：有N个村庄，从1-N标记，需要修建一些路从而使每个村庄都可以相互到达。这里的到达的意思是，A与B
相连，B与C相连，则A与C也相连。
题目给定了一些已经修建好的路，需要再修建一些路，使所修的路程最短。
这就是一个最小生成树，但是得保证已经修好的路必须被选上。
我用的prim算法，开始的思路就是在每次搜索与已经选定的点集最近距离的点的时候，先搜索是否有必须
得选择的边，有的话就选择它，否则就按prim算法本来的步骤进行。感觉这样应该是对的，但是按这种思路竟
然wa了，我自己也不知道错在哪里。纠结了很久后果断去看了discuss，原来只需要把已经修建好的边的路程
改为0，这样每次都会优先选择修建好的边，刚好最后的所有被选中的边的总长就是答案。
<div class="cnblogs_code"> 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 const int maxn=103; 6 const int INF=1<<30; 7 int ans; 8 int dist,map,pre; 9 void Prim(int n)10 {11 int Min;12 bool p;13 ans=0;14 for(int i=2; i<=n; i++)15 {16 p=false;17 dist=map[1];18 pre=1;19 }20 dist[1]=0;21 p[1]=true;22 int k;23 for(int i=1; i<n; i++)24 {25 Min=INF;26 k=0;27 for(int j=1; j<=n; j++)28 {29 if(!p && dist<Min)30 {31 Min=dist;32 k=j;33 }34 }35 if(k==0)return;36 ans+=Min;37 p=true;38 for(int j=1; j<=n; j++)39 {40 if(!p && map<INF && dist>map)41 {42 dist=map;43 pre=k;44 }45 }46 }47 }48 int main()49 {50 int n,q;51 int a,b;52 // freopen("in.txt","r",stdin);53 while(scanf("%d",&n)!=EOF)54 {55 for(int i=1; i<=n; i++)56 for(int j=1; j<=n; j++)57 scanf("%d",&map);58 scanf("%d",&q);59 for(int i=1; i<=q; i++)60 {61 scanf("%d%d",&a,&b);62 map=map=0;63 }64 Prim(n);65 printf("%d\n",ans);66 }67 return 0;68 }
页:
[1]