【题目链接】http://poj.org/problem?id=3164
【解题思路】百度百科:最小树形图 】里面有详细的解释,而Notonlysucess有精简的模板,下文有对其模板的一点解释,前提是对朱刘算法有所了解
【PS】这题没必要写题解,学了朱刘算法并不是表示你就锻炼到了思维了,在看最小树形图的形成时,对缩点那部分内容的算法和思路感叹不已,我想这就是算法的魅力!!
要理解的话,最好结合那张转载得很疯狂的图,但单看不行,自己将每个过程手动笔画一下更容易理解,开始搜题解的时候几乎都是用了模板,本来也想理解之后靠模板过了就算了以后如果遇到了这类题,二话不说直接上模板,后来自己还是手动的敲了一下,在OJ上提交了不差20次吧~~
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#define SIZE 102
#define MAXN 1 << 14 using namespace std; const double inf = << ;
const double eps = 1e-;
int nv, m, ne, root, cnt; struct Edge{
int u, v;
double cost;
};
struct Edge edge[MAXN];
double x[SIZE], y[SIZE];
int vis[SIZE];
int circle_id[SIZE];
double node[SIZE][SIZE];
double in[SIZE];
int pre[SIZE]; double dis(int a, int b)
{
return sqrt((x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b]));
} void dfs(int cur)
{
vis[cur] = ;
for(int i=; i<=nv; ++i)
if(!vis[i] && node[cur][i] > inf)
dfs(i);
} bool exit_circle(double& res)
{
int update_id = ;
memset(vis, -, sizeof(vis));
memset(circle_id, -, sizeof(circle_id));
in[root] = ;
for(int i=; i<=nv; ++i)
{
res += in[i];
int v = i;
while(vis[v] != i && circle_id[v] == - && v != root)
{
vis[v] = i;
v = pre[v];
}
if(vis[v] == i)
{
for(int u = pre[v]; u != v; u = pre[u])
circle_id[u] = update_id;
circle_id[v] = update_id++;
}
}
if(update_id == ) return true;
for(int i=; i <= nv; ++i)
if(circle_id[i] == -)
circle_id[i] = update_id++; for(int i=; i < ne; ++i)
{
int u = edge[i].u;
int v = edge[i].v;
edge[i].u = circle_id[u];
edge[i].v = circle_id[v];
if(edge[i].u != edge[i].v) edge[i].cost -= in[v];
}
nv = update_id - ;
root = circle_id[root];
return false;
} bool insert()
{
for(int i=; i<=nv; ++i) in[i] = inf;
for(int i=; i<ne; ++i)
{
int& e = edge[i].v;
if(e == root) continue;
if(e != edge[i].u && in[e] > edge[i].cost)
{
in[e] = edge[i].cost;
pre[e] = edge[i].u;
}
}
for(int i=; i <= nv; ++i)
if(i != root && inf - in[i] < eps) return false;
return true;
} int main()
{
while(scanf("%d%d", &nv, &ne) != EOF)
{
for(int i=; i<=nv; ++i)
scanf("%lf%lf", &x[i], &y[i]);
cnt = ;
memset(node, , sizeof(node));
for(int i=; i<ne; ++i)
{
int u, v;
scanf("%d%d", &u, &v);
if(u != v)
edge[i].cost = dis(u, v);
else
edge[i].cost = inf;
edge[i].u = u;
edge[i].v = v;
}
root = ;
bool flag = false;
double ans = ;
do
{
if(!insert())
{
flag = true;
break;
}
}while(!exit_circle(ans));
if(flag) printf("poor snoopy\n");
else printf("%.2f\n", ans);
}
return ;
}
#include<cstdio>
#include<cstring>
#include<cmath>
#define SIZE 104
#define MAXN 10002 using namespace std; const double esp = 1e-;
const double inf = <<; int nv, ne; struct Edge{
int v, u;
double cost;
}edge[MAXN]; int vis[SIZE], circle_id[SIZE];
int pre[SIZE];
double in[SIZE];
double x[SIZE], y[SIZE]; double dis(int v, int u)
{
return sqrt((x[v]-x[u])*(x[v]-x[u]) + (y[v]-y[u])*(y[v]-y[u]));
} bool Traverse(double& res)
{//基本来自于模板
int root = ;
while(true)
{
for(int i = ; i <= nv; ++i) in[i] = inf+SIZE;
for(int i = ; i < ne; ++i)
{//集当前结点的各自最小的入边
int& u = edge[i].u;
if(in[u] > edge[i].cost && u != edge[i].v)
{
in[u] = edge[i].cost;
pre[u] = edge[i].v;
}
}
//在当前情况下如果有任何一个点没有最小边,说明不能形成最小树形图
//但这里没必要每次都判断,只在第一次进行判断即可
for(int i = ; i <= nv; ++i)
if(i != root && in[i] > inf) return false; int credit = ;
in[root] = ;
memset(vis, -, sizeof(vis));
memset(circle_id, -, sizeof(vis));
for(int i = ; i <= nv; ++i)
{//res为什么可以一直在加,首先第一次其就将有环没环的【结点最小边】的权值都加了,但就像缩点的理由所说的一样
//环中没必要加的一条边再后来的减掉了,看下面的 ‘##’处
res += in[i];
int v = i;
while(vis[v] != i && circle_id[v] == - && v != root)
{//这里并不能将 circle_id[v] == -1 这个条件提取出来提前判断
//一个结点假设其不在环内,那么其结果是退后到根点或者退后到一个结点是环内点(已判断其为环内的点)
vis[v] = i;
v = pre[v];
}
if(vis[v] == i)
{//其实这里已经在缩点,将环内的点写入一个统一的结点编号
for(int u = pre[v]; u != v; u = pre[u])
circle_id[u] = credit;
circle_id[v] = credit++;
}
}
if(credit == ) return true;
for(int i = ; i <= nv; ++i)
if(circle_id[i] == -) circle_id[i] = credit++;
for(int i = ; i < ne; ++i)
{//如果更新后两个结点有相同的编号,其作用体现在上面求最小边中 :u != edge[i].v的判断
int u = edge[i].u;
int v = edge[i].v;
edge[i].u = circle_id[u];
edge[i].v = circle_id[v];
// ## 如果这条最小边不在环内(即这里判断的意义),因为之前加了最小边的值,那就得减去其值。
//那么减掉之后就可能变成了零或比之前短 ;其实这里不用判断条件的 如果是在环内
//其因为两端的结点相同对后来没有了影响,这是剩下最后一种情况了,就是一结点在环内(能缩点的条件)
if(edge[i].v != edge[i].u)
edge[i].cost -= in[u];
}
nv = credit - ;
root = circle_id[root];
}
return true;
} int main()
{
while(scanf("%d%d", &nv, &ne) != EOF)
{
for(int i = ; i <= nv; ++i)
scanf("%lf%lf", &x[i], &y[i]);
for(int i = ; i < ne; ++i)
{//这里就开始处理掉自环的情况,把自环的距离设置得比预定的最大值还大
scanf("%d%d", &edge[i].v, &edge[i].u);
edge[i].cost = edge[i].v == edge[i].u ? inf+MAXN : dis(edge[i].v, edge[i].u);
}
double res = ;
if(Traverse(res)) printf("%.2f\n", res); //这里用f好像跟提交的方式有关,FAQ里有解释
else printf("poor snoopy\n");
}
return ;
}