kuangbin专题八 POJ3164 Command Network（最小树形图的理解+模板）

本文主要是介绍kuangbin专题八 POJ3164 Command Network（最小树形图的理解+模板），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
给你N个点的坐标，然后给你M条单向边的信息，A,B表示A指向B，从1开始，1的信息能传达到所有的点。
题解：
一开始这道题我看到了单向边，还想着怎么把他变成双向边来做prim算法，后来实在想不到，去看了题解，发现这道题原来是一个最小树形图。。。ORZ，对于这个算法的理解我还是看了别的大佬的博客才弄懂的，看算法的话可以参考一下这个大佬的：http://blog.csdn.net/wsniyufang/article/details/6747392
然后要想看的通俗点的话就看一下这个大佬的博客：
http://blog.csdn.net/sdj222555/article/details/7459738

再之后是我自己对于上面两位大佬的讲解进行的理解：

（朱刘算法）最小树形图是求有向边的最小生成树的算法。
算法步骤如下：
1.判断图的连通性，若不连通直接无解，否则一定有解。
2.为除了根节点以外的所有点选择一个权值最小的入边，假设用pre数组记录前驱，f数组记录选择的边长，记所选边权和为temp。
3.（可利用并查集）判断选择的的边是否构成环，若没有则直接ans+=temp并输出ans，若有，则进行下一步操作。
4.对该环实施缩点操作，设该环上有点V1，V2……Vi……Vn，缩成的点为node?，对于所有不在环中的点P进行如下更改：
（1）点P到node的距离为min{a[p,Vi]-f[Vi]} (a为边集数组)
（2）点node到p的距离为min{a[Vi,p]}
操作（1）的理解：先假设环上所有边均选上，若下次选择某一条边进入该环，则可以断开进入点与进入点的前驱之间的边，即断开F[进入点]，所以等效为直接把a[p,node]赋值为min{a[p,Vi]-f[Vi]}。

算法中的a[p,vi]的意思是点p指向vi的长度，第四步中（1）通俗的理解的话可以这样想：
举个例子：某个图的部分图中， 1->2权值为3， 2->1权值为4， 3->1权值为9， 4->2权值为7。那么可以看到，结点1和结点2是形成了一个环的。
我们仅从其大小是不知道该删除哪条边比较好（这个就好像无向图联通三个点，1<->3权值为100，1<->2权值为1，2<->3权值为5，一开始从1走，判断2与3，你能马上确定不要1<->3这条边吗？），
这时看到3->1权值为9，如果走这条边，那么接下来只能删除掉2->1这条边，同理走4->2的话就要删除掉1->2这条边。那么就不妨建立新图，将1和2缩成一点，3->1的权值就变成了9-4=5， 4->2的权值变成了7-3=4。这样的话，
就相当于变相删除了不需要走的边了（我来说一下我的理解，1和2缩点之后，3->1的权值为什么要9-4=5，因为你要在有向图中联通4个点的话，3连到1，而你不能要2->1,而应该要1->2的边的吧？因为你要2->1的话就会出现3能通1不能通2的尴尬情况，这对于要联通整个图是不合理的，到这里懂了吧？同理4->2的权值变成7-3=4也应该能理解了吧？如果选择1->2的话就会出现4通2不通1的情况了。所以减去那些入边的操作实际上是为了删除不需要的边）。
形成新图后，又变成了最小树形图的求解，就这样循环下去，直到图中的最小边集没有环为止。

//大佬的模板,ORZ
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
const int MAXN=105;
struct node1
{int u,v;double w;
}map[MAXN*MAXN];
struct node2
{double x,y;
}p[MAXN];
double IN[MAXN];
int pre[MAXN];
int ID[MAXN];
int vis[MAXN];
int n,m;
double zhuliu_mst(int root,int V,int E)
{memset(pre,0,sizeof(pre));double sum=0;while(true){//1.找最小入边for(int i=1;i<=V;i++) IN[i]=INF*1.0;for(int i=1;i<=E;i++){int u=map[i].u;int v=map[i].v;if(map[i].w<IN[v]&&u!=v){pre[v]=u;IN[v]=map[i].w;}}for(int i=1;i<=V;i++){if(i==root) continue;if(IN[i]==INF*1.0) return -1;//除了根以外的点没有入边,则根无法到达该点 }//2找环int cnt=1;memset(ID,0,sizeof(ID));memset(vis,0,sizeof(vis));IN[root]=0;for(int i=1;i<=V;i++)//标记每个环 {sum+=IN[i];int v=i;while(vis[v]!=i&&!ID[v]&&v!=root){vis[v]=i;v=pre[v];}if(v!=root&&!ID[v]){for(int u=pre[v];u!=v;u=pre[u]){ID[u]=cnt;}ID[v]=cnt++; } }if(cnt==1) break;//无环for(int i=1;i<=V;i++){if(!ID[i])ID[i]=cnt++;}//3.缩点,重新标记for(int i=1;i<=E;i++){int v=map[i].v;int u=map[i].u;map[i].u=ID[u];map[i].v=ID[v];if(ID[u]!=ID[v]){map[i].w-=IN[v];}}V=cnt-1;//为什么要-1,因为是从1开始标记的，i++之后会多出1，所以要减去1 root=ID[root];}return sum;
}
int main()
{while(~scanf("%d%d",&n,&m)){for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);for(int i=1;i<=m;i++){scanf("%d%d",&map[i].u,&map[i].v);if(map[i].u!=map[i].v)map[i].w=sqrt((p[map[i].u].x-p[map[i].v].x)*(p[map[i].u].x-p[map[i].v].x)+(p[map[i].u].y-p[map[i].v].y)*(p[map[i].u].y-p[map[i].v].y));elsemap[i].w=INF;}double ans=zhuliu_mst(1,n,m);if(ans==-1)printf("poor snoopy\n");elseprintf("%.2f\n",ans);}return 0;
}