原題：
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’.
一開始沒仔細(xì)讀題，一看以為是最小生成樹呢，結(jié)果Krusal算法上去WA了，Prim算法也WA,修修改改一直WA，第二天發(fā)現(xiàn)本題是要在有向圖上面構(gòu)造最小樹形圖。
按照著名的Zhu-Liu算法，仔細(xì)實(shí)現(xiàn)了一邊，終于AC了。
按照我的理解總結(jié)下該算法，該算法對每個結(jié)點(diǎn)，除根節(jié)點(diǎn)外尋找最小入邊，
1）如果這些入邊不構(gòu)成環(huán)，那么容易證明這些邊構(gòu)成最小樹形圖。
證明：設(shè)加上根節(jié)點(diǎn)r一共N個點(diǎn)，那么一共有N-1條邊，證明從r能到每個點(diǎn)，若存在一點(diǎn)v，使得從r到v沒有路徑，那么，假設(shè)從v反向回退必然構(gòu)成環(huán)，因?yàn)槊總€點(diǎn)除了r都有入邊，如果不構(gòu)成環(huán)，該路徑可以無窮大。
2）如果存在環(huán)，我們把環(huán)收縮成一個點(diǎn)，更新相應(yīng)的入邊和出邊，得到新的圖G',使得原問題在G'中等效：
怎么收縮呢？
假設(shè)我們把環(huán)收縮成環(huán)上的任意一點(diǎn)v，所有進(jìn)環(huán)的邊和出環(huán)的邊自動變成v的邊（如果已有，取長度最短的），其余點(diǎn)標(biāo)記為刪除，更新不在環(huán)上的所有點(diǎn)進(jìn)入該環(huán)的長度cost為cost-cost(prev[x],x);其中點(diǎn)x為進(jìn)入環(huán)的邊在環(huán)上的端點(diǎn)。出邊保持不變。
這里為什么這么更新？因?yàn)檫@樣更新使得我們的算法在新圖上是等效的。任何環(huán)的解決后意味著在新圖里面得為改收縮后的點(diǎn)尋找新的入邊，而實(shí)際的花費(fèi)應(yīng)該是新的入邊減去原有的入邊長度，我們的算法在找到環(huán)的時候就把環(huán)上所有的邊的長度計(jì)算在花費(fèi)內(nèi)了.而對出邊是沒有影響的。
到這算法的框架基本出來了。當(dāng)為某點(diǎn)沒找到入邊的時候，意味著無解。為了加快無解的偵測，我們先運(yùn)行一遍DFS搜索，假如從根節(jié)點(diǎn)出發(fā)，可觸及的節(jié)點(diǎn)數(shù)小于N-1(不含r)則意味著無解。反之，肯定有解。
為什么？
因?yàn)槿绻捎|及數(shù)小于N-1,意味著某點(diǎn)是不可觸及的，也就是原圖不是弱連通。對該點(diǎn)來說不存在從r到它的路徑。反之，從r到某點(diǎn)都有一條路徑，沿著該路徑就能找到結(jié)點(diǎn)的入邊。
第二個問題是，如何快速偵測環(huán)呢？
我使用了一個不相交集。回憶Krusal的算法實(shí)現(xiàn)里面也是使用不相交集來避免找產(chǎn)生環(huán)的最小邊。
下面是我的代碼：
// 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);
}
}