题目链接:
http://poj.org/problem?id=3164
题目大意:
有n个点(用坐标表示)各点编号分别为1—>n,m条单向路,问能否存在一个花费价值最小的网络,能使从1点到达任一个点。
解题思路:
很明显的朱刘模板题,但是刚看到这个题目的时候,弱还不懂这个东西%>_<%
最小树形图就是给有向带权图中指定一个特殊的点root,求一棵以root为根的有向生成树T,并且T中所有边的总权值最小。
朱刘算法:当有向图中不存在自环,为除根之外的每个点选定一条入边,这条入边一定要是所有入边中最小的。所有的最小入边都选择出来了,如果这个入边集不存在有向环的话,这个集合就是该图的最小树形图。如果有自环的话就要消除自环,比如,现在我们假设分别有3-->1,权值为1 . 1-->3,权值为2 . 2-->1,权值为6 . 4-->3,权值为5. ,root为点4,存在自环1-->3-->1,现在就需要把1,3缩成一个点,则需要把4-->3边的权值5-2,2-->1边的权值变为6-1,。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = ;
const int N = ;
const double Exp = 1e-;
const int INF = 0x3f3f3f3f;
struct Point
{
double x, y;
double length(Point a)
{
return sqrt((a.x-x)*(a.x-x)+(a.y-y)*(a.y-y));
}
}; struct Edge
{
int u, v;
double w;
}; Point point[maxn];
Edge edge[N];
int n, m;
double directed_MST (int root)
{
double pre[maxn], ans = ;
//pre[i]为到i点权值最小的边值
int vis[maxn], id[maxn], pr[maxn];
//vis[i]为i点是否在当前的数上,id[i]为i点是否在自环内,
int u, v;
while (true)
{
for (int i=; i<=n; i++)
pre[i] = INF;
for (int i=; i<m; i++)
{
u = edge[i].u;
v = edge[i].v;
if (edge[i].w<pre[v] && u!=v)
{
pre[v] = edge[i].w;
pr[v] = u;//到v点前驱
}
}
for (int i=; i<=n; i++)
{
if (i == root)
continue;
if (pre[i] == INF)
return -;//没有点与i相连,不存在最小树形图
}
memset (vis, -, sizeof(vis));
memset (id, -, sizeof(id));
int cru = ;//对现存的点从新编号
pre[root] = ;
for (int i=; i<=n; i++)
{
ans += pre[i];
v = i;
while (vis[v]!=i && id[v]==- && v!=root)
{//向树上加点
vis[v] = i;
v = pr[v];
}
if (v!=root && id[v]==-)
{//存在自环,并且把环变成一个点
for (u=pr[v]; u!=v; u=pr[u])
id[u] = cru;
id[u] = cru ++;
}
}
if (cru == )
break;//不存在自环
for (int i=; i<=n; i++)
if (id[i] == -)
id[i] = cru ++;//对不在自环上的点编号
for (int i=; i<m; i++)
{//把自环缩成一个点后,需要改变边的权
u = edge[i].u;
v = edge[i].v;
edge[i].u = id[u];
edge[i].v = id[v];
if (id[u] != id[v])
edge[i].w -= pre[v];
}//缩点后点数改变,根节点改变
n = cru - ;
root = id[root];
}
return ans;
}
int main ()
{
while (scanf ("%d %d", &n, &m) != EOF)
{
for (int i=; i<=n; i++)
scanf ("%lf %lf", &point[i].x, &point[i].y); for (int i=; i<m; i++)
{
int u, v;
scanf ("%d %d", &u, &v);
edge[i].u = u;
edge[i].v = v;
if (u == v)
edge[i].w = INF;
else
edge[i].w = point[u].length(point[v]);
}
double num = directed_MST();
if (num+< Exp)
printf ("poor snoopy\n");
else
printf ("%.2f\n", num);
}
return ;
}