题目地址：POJ 3164 最小树形图第一发。 把一个v写成u了。。。。。TLE了一晚上。。。（虽说今晚出去玩了。。） 刚开始看这个算法的时看模板以为又是一个isap。。。。吓得一个哆嗦。但是仔细看了看之后发现还是挺好理解的。写下自己的理解。 朱刘算法其实只有3步，然后不断循环。 1：找到每个点的最小入边。既然是生成树，那么对于每个点来说，只要选一个权值最小的入边就可以了。贪心思想。因为如果不是最小入边，那么它肯定不是最小树形图的一条边，考虑它是没有意义的。 2：找环。找环找的是最小入边构成的新图的环。如果没找到环，那么一棵树就已经形成了，因为树就是没有环的图。再因为边权都是最小的，因此此时最小树形图就已经出来了，停止循环。 3：如果第2步中找到了环，那么这个环就可以缩成一个点。然后构造新图，更新边权。更新边权的方法是：假设某点u在该环上，并设这个环中指向u的边权是in[u]，那么对于每条从u出发的边(u, i, w)，在新图中连接(new, i, w)的边，其中new为新加的人工顶点; 对于每条进入u的边(i, u, w)，在新图中建立边(i, new, w-in[u])的边。之所以是w-in[u]的原因是如果选择了w，那么那个in[u]在树中就是多余的，完全可以删除，所以需要减去，然后再后面的总费用累加中会体现出删掉了这个权值，不理解的画个图就明白了。 至于实现方法还是看代码吧。看不懂的可以留言提问。 代码如下：
;mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=40000+10;int cnt, n;int color[110], id[110], pre[110];double in[200];struct Point{double x, y;}fei[200];struct node{int u, v;double w;}edge[11000];void add(int u, int v, double w){edge[cnt].u=u;edge[cnt].v=v;edge[cnt++].w=w;}double dist(Point f1, Point f2){return sqrt((f1.x-f2.x)*(f1.x-f2.x)*1.0+(f1.y-f2.y)*(f1.y-f2.y));}double dmst(int root){double ans=0;int i, j, u, v, NV=n;while(1){for(i=1;i<=NV;i++) in[i]=INF;//找最小入边for(i=0;i<cnt;i++){u=edge[i].u;v=edge[i].v;if(v!=u&&edge[i].w<in[v]){//更新最下入边，并设为前驱节点in[v]=edge[i].w;pre[v]=u;}}for(i=1;i<=NV;i++){if(i!=root&&in[i]==INF) return -1;//有孤立点，不可能生成树}memset(color,-1,sizeof(color));memset(id,-1,sizeof(id));in[root]=0;int tot=0;for(i=1;i<=NV;i++){ans+=in[i];u=i;while(color[u]!=i&&id[u]==-1&&u!=root){//找环color[u]=i;u=pre[u];}if(id[u]==-1&&u!=root){//惊现一只环！快活捉他。。id[u]=++tot;//对发现的环进行编号，相当于缩点后的那个点。for(v=pre[u];v!=u;v=pre[v]){id[v]=tot;}}}if(!tot) break;//没找到环，说明大功告成。那就收拾东西走人吧。。for(i=1;i<=NV;i++){if(id[i]==-1) id[i]=++tot;//对所有点进行编号，，一个都不能跑。。}for(i=0;i<cnt;i++){//更新边权，构造新图v=edge[i].v;edge[i].u=id[edge[i].u];edge[i].v=id[edge[i].v];if(edge[i].u!=edge[i].v){edge[i].w-=in[v];}}NV=tot;root=id[root];//不要忘记更新点数和树根的编号。。}return ans;}int main(){int m, i, j, u, v;double ans;while(~scanf(“%d%d”,&n,&m)){for(i=1;i<=n;i++){scanf(“%lf%lf”,&fei[i].x,&fei[i].y);}cnt=0;while(m–){scanf(“%d%d”,&u,&v);if(u!=v)add(u,v,dist(fei[u],fei[v]));}ans=dmst(1);if(ans==-1) puts(“poor snoopy”);else printf(“%.2f\n”,ans);}return 0;}
回避现实的人，未来将更不理想。
