学步园

下午看到了这题，第一反应就是MST,既然是MST,可以用Kruskal快速地解决问题，记住在输入所有边之后，删除村庄时把边删除，我的方法是开一个数组ext，ext[i]表示i是否存在，在对边结构体排序的时候，把不存在的边通通放到后面去，这样，当Kruskal过程中，找到一个不存在的边时，就退出，这样会节省比较多的时间。

并查集初始化的时候要全部初始化，以防出现不用的情况。

#include <iostream><br /> #include <cstdio><br /> #include <cstring><br /> #include <cstdlib><br /> #include <algorithm></p> <p>using namespace std;</p> <p>const int MAX=210;<br /> int n,cnt,ret;<br /> int p[MAX],rank[MAX];<br /> bool ext[MAX];<br /> struct Edge<br /> {<br /> int from;<br /> int to;<br /> int weight;</p> <p> bool operator<(const Edge& edge) const<br /> {<br /> if(ext[from]==false||ext[to]==false)<br /> return false;<br /> if(ext[edge.from]==false||ext[edge.to]==false)<br /> return true;<br /> return weight<edge.weight;<br /> }<br /> }edge[MAX*MAX];</p> <p>void Init()<br /> {<br /> for(int i=0;i<210;i++)<br /> {<br /> p[i]=i;<br /> rank[i]=0;<br /> }<br /> }</p> <p>void Link(int x,int y)<br /> {<br /> if(rank[x]<rank[y])<br /> p[x]=y;<br /> else<br /> {<br /> p[y]=x;<br /> if(rank[x]==rank[y])<br /> rank[x]++;<br /> }<br /> }</p> <p>int Find(int x)<br /> {<br /> if(p[x]!=x)<br /> p[x]=Find(p[x]);</p> <p> return p[x];<br /> }</p> <p>void Union(int x,int y)<br /> {<br /> Link(Find(x),Find(y));<br /> }</p> <p>bool Kruskal()<br /> {<br /> sort(edge,edge+cnt);<br /> int done=0;</p> <p> Init();</p> <p> for(int i=0;i<cnt&&done<n-1;i++)<br /> {<br /> if(ext[edge[i].from]==false||ext[edge[i].to]==false)<br /> break;<br /> if(Find(edge[i].from)!=Find(edge[i].to))<br /> {<br /> done++;<br /> ret+=edge[i].weight;<br /> Union(edge[i].from,edge[i].to);<br /> }<br /> }</p> <p> if(done==n-1)<br /> return true;<br /> else<br /> return false;<br /> }</p> <p>int main()<br /> {<br /> int t;<br /> int x,y,w;<br /> int nn,ee,m;</p> <p> scanf("%d",&t);<br /> while(t--)<br /> {<br /> cnt=0;<br /> ret=0;<br /> memset(ext,0,sizeof(ext));<br /> scanf("%d%d",&nn,&ee);<br /> n=nn;<br /> for(int i=0;i<nn;i++)<br /> ext[i]=true;<br /> for(int i=0;i<ee;i++)<br /> {<br /> scanf("%d%d%D",&x,&y,&w);<br /> edge[cnt].from=x;<br /> edge[cnt].to=y;<br /> edge[cnt].weight=w;<br /> cnt++;<br /> }</p> <p> scanf("%d%d",&nn,&ee);<br /> for(int i=n;i<n+nn;i++)<br /> ext[i]=true;<br /> n+=nn;<br /> for(int i=0;i<ee;i++)<br /> {<br /> scanf("%d%d%D",&x,&y,&w);<br /> edge[cnt].from=x;<br /> edge[cnt].to=y;<br /> edge[cnt].weight=w;<br /> cnt++;<br /> }</p> <p> scanf("%d",&m);<br /> n-=m;<br /> for(int i=0;i<m;i++)<br /> {<br /> scanf("%d",&x);<br /> ext[x]=false;<br /> }</p> <p> if(Kruskal())<br /> printf("%d/n",ret);<br /> else<br /> printf("what a pity!/n");<br /> }</p> <p> return 0;<br /> }<br />