原题：
Command Network
Description
After
a long lasting war on words, a war on arms finally breaks out between
littleken’s and KnuthOcean’s kingdoms. A sudden and violent assault by
KnuthOcean’s force has rendered a total failure of littleken’s command
network. A provisional network must be built immediately. littleken
orders snoopy to take charge of the project.
With the situation
studied to every detail, snoopy believes that the most urgent point is
to enable littenken’s commands to reach every disconnected node in the
destroyed network and decides on a plan to build a unidirectional
communication network. The nodes are distributed on a plane. If
littleken’s commands are to be able to be delivered directly from a
node A to another node B, a wire will have to be built along the
straight line segment connecting the two nodes. Since it’s in wartime,
not between all pairs of nodes can wires be built. snoopy wants the
plan to require the shortest total length of wires so that the
construction can be done very soon.
Input
The input contains several test cases. Each test case starts with a line containing two integer N (N ≤ 100), the number of nodes in the destroyed network, and M (M ≤ 104), the number of pairs of nodes between which a wire can be built. The next N lines each contain an ordered pair xi and yi, giving the Cartesian coordinates of the nodes. Then follow M lines each containing two integers i and j between 1 and N (inclusive) meaning a wire can be built between node i and node j
for unidirectional command delivery from the former to the latter.
littleken’s headquarter is always located at node 1. Process to end of
file.
Output
For
each test case, output exactly one line containing the shortest total
length of wires to two digits past the decimal point. In the cases that
such a network does not exist, just output ‘poor snoopy’.
一开始没仔细读题，一看以为是最小生成树呢，结果Krusal算法上去WA了，Prim算法也WA,修修改改一直WA，第二天发现本题是要在有向图上面构造最小树形图。
按照著名的Zhu-Liu算法，仔细实现了一边，终于AC了。
按照我的理解总结下该算法，该算法对每个结点，除根节点外寻找最小入边，
1）如果这些入边不构成环，那么容易证明这些边构成最小树形图。
证明：设加上根节点r一共N个点，那么一共有N-1条边，证明从r能到每个点，若存在一点v，使得从r到v没有路径，那么，假设从v反向回退必然构成环，因为每个点除了r都有入边，如果不构成环，该路径可以无穷大。
2）如果存在环，我们把环收缩成一个点，更新相应的入边和出边，得到新的图G',使得原问题在G'中等效：
怎么收缩呢？
假设我们把环收缩成环上的任意一点v，所有进环的边和出环的边自动变成v的边（如果已有，取长度最短的），其余点标记为删除，更新不在环上的所有点进入该环的长度cost为cost-cost(prev[x],x);其中点x为进入环的边在环上的端点。出边保持不变。
这里为什么这么更新？因为这样更新使得我们的算法在新图上是等效的。任何环的解决后意味着在新图里面得为改收缩后的点寻找新的入边，而实际的花费应该是新的入边减去原有的入边长度，我们的算法在找到环的时候就把环上所有的边的长度计算在花费内了.而对出边是没有影响的。
到这算法的框架基本出来了。当为某点没找到入边的时候，意味着无解。为了加快无解的侦测，我们先运行一遍DFS搜索，假如从根节点出发，可触及的节点数小于N-1(不含r)则意味着无解。反之，肯定有解。
为什么？
因为如果可触及数小于N-1,意味着某点是不可触及的，也就是原图不是弱连通。对该点来说不存在从r到它的路径。反之，从r到某点都有一条路径，沿着该路径就能找到结点的入边。
第二个问题是，如何快速侦测环呢？
我使用了一个不相交集。回忆Krusal的算法实现里面也是使用不相交集来避免找产生环的最小边。
下面是我的代码：
// 3164.cpp : Defines the entry point for the console application.
//
#include <iostream>
#include <cmath>
using namespace std;
typedef struct _Point
{
double x;
double y;
double distanceTo(const struct _Point& r)
{
return sqrt((x-r.x)*(x-r.x)+(y-r.y)*(y-r.y));
}
}Point;
const int MAX_V=100;
const int MAX_E=10000;
const double NO_EDGE=1.7976931348623158e+308;
Point vertexes[MAX_V]={0};
int parents[MAX_V]={0};
int ranks[MAX_V]={0};
double G[MAX_V][MAX_V]={0};
bool visited[MAX_V]={0};
bool deleted[MAX_V]={0};
int prev[MAX_V]={0};
int nVertex=0;
int nEdge=0;
int u_find(int a)
{
if(parents[a]==a)return a;
parents[a]=u_find(parents[a]);
return parents[a];
}
void u_union(int a,int b)
{
int pa=u_find(a);
int pb=u_find(b);
if(ranks[pa]==ranks[pb])
{
ranks[pa]++;
parents[pb]=pa;
}else if(ranks[pa]<ranks[pb])
{
parents[pa]=pb;
}
else
{
parents[pb]=pa;
}
}
void DFS(int v,int& c)
{
visited[v]=true;
for(int i=1;i<nVertex;i++)
{
if(!visited[i]&&G[v][i]<NO_EDGE)
{
c+=1;
DFS(i,c);
}
}
}
void doCycle(int s,int t,double& cost)
{
memset(visited,0,sizeof(bool)*nVertex);
int i=s;
do
{
visited[i]=true;
cost+=G[prev[i]-1][i];
//cout<<"from "<<(prev[i]-1)<<" to "<<i<<" (cycle)"<<" weight:"<<G[prev[i]-1][i]<<endl;
i=prev[i]-1;
}while(i!=s);
do
{
for(int k=0;k<nVertex;k++)
{
if(!deleted[k]&&!visited[k])
{
if(G[k][i]<NO_EDGE)
{
if(G[k][i]-G[prev[i]-1][i]<G[k][s])
{
G[k][s]=G[k][i]-G[prev[i]-1][i];
//cout<<"1.update ["<<k<<","<<s<<"] at "<<i<<" as "<<G[k][s]<<endl;
}
}
if(G[i][k]<NO_EDGE)
{
if(G[i][k]<G[s][k])
{
G[s][k]=G[i][k];
//cout<<"2.update ["<<s<<","<<k<<"] at "<<i<<" as "<<G[s][k]<<endl;
}
}
}
}
if(i!=s)
{
deleted[i]=true;
//cout<<"mark "<<i<<" as deleted"<<endl;
}
i=prev[i]-1;
}while(i!=s);
}
int main(void)
{
while(cin>>nVertex>>nEdge)
{
int s,t;
int nv=0;
bool cycle=0;
double cost=0;
memset(vertexes,0,sizeof(vertexes));
memset(visited,0,sizeof(visited) );
memset(deleted,0,sizeof(deleted));
memset(G,0,sizeof(G));
memset(prev,0,sizeof(prev));
memset(ranks,0,sizeof(ranks));
memset(parents,0,sizeof(parents));
for(int i=0;i<nVertex;i++)
{
cin>>vertexes[i].x>>vertexes[i].y;
parents[i]=i;
for(int j=0;j<nVertex;j++)
{
G[i][j]=NO_EDGE;
}
}
for(int i=0;i<nEdge;i++)
{
cin>>s>>t;
if(t==1||s==t)continue;
G[s-1][t-1]=vertexes[s-1].distanceTo(vertexes[t-1]);
}
DFS(0,nv);
if(nv<nVertex-1)
{
cout<<"poor snoopy"<<endl;
continue;
}
do {
cycle=false;
for(int i=0;i<nVertex;i++){parents[i]=i;}
memset(ranks,0,sizeof(bool)*nVertex);
for (int i = 1; i < nVertex; i++) {
double minimum=NO_EDGE;
if(deleted[i])continue;
for(int k=0;k<nVertex;k++)
{
if(!deleted[k]&&minimum>G[k][i])
{
prev[i]=k+1;
minimum=G[k][i];
}
}
if(minimum==NO_EDGE)
{
throw 1;
}
if (u_find(prev[i]-1) == u_find(i)) {
doCycle(prev[i]-1,i, cost);
cycle = true;
break;
}
else
{
u_union(i,prev[i]-1);
}
}
} while (cycle);
for (int i = 1; i < nVertex; i++) {
if(!deleted[i])
{
cost+=G[prev[i]-1][i];
//cout<<"from "<<(prev[i]-1)<<" to "<<i<<" weight:"<<G[prev[i]-1][i]<<endl;
}
}
printf("%.2f\n",cost);
}
}