2 3

poor snoopy

POJ Monthly--2006.12.31, galaxy

题目大意：长时间战争过后，一场战争终于切断了Littleken和KnuthOcean王国的联系。

Littleken的指挥网络瘫痪了，现在最重要的事是建立一个临时的通信网络，这个任务交

给了Snoopy。

Snoopy觉得最重要的一点是要把命令传到被摧毁的网络中的每一个点上，所以他决定先

建立一个单向的传输网络。假设所有的传输节点都分布在一个平面上。如果Littleken的

命令想要从节点A传送到节点B上，必须建立一个单向电缆从节点A连接到节点B。为了

尽可能节省资源，要求通信网络所用的电缆长度最小(参考ACM-ICPC程序设计系列)。

现在给你N个点坐标(x,y)，M条可以架设有向电缆的路。求：至少需要的电缆长度。如果

不能建立这样的通信网，就输出"poor snoopy"。

思路：理解题目意思后，就转换为给你一个有向图，求有向图的最小树形图。在这里要用

到朱刘算法(终于见到我们中国人自己写出的算法了)。具体步骤如下：

朱刘算法(Edmonds)：

基于贪心和缩点的思想。

假设根的顶点是V0。

(1)除了根结点外，所有的点Vi，找到以Vi为终点的最短的边，加入集合中

（pre[v]存放的是终点v的起点,In[v]存放终点为v的最短的边）

(2)检查集合中有没有有向环和收缩点。若没有有向环和收缩点，结束计算；若没有有向环、

但含收缩边，则跳至步骤(4)；若含有有向环，则跳至步骤(3)。

(3)含有有向环，则收缩有向环(缩点)，把有向环收缩为一个点，其有向环内的边被收缩掉，而环外的边被保

留，构建新图，重复步骤(1)、(2)。

(4)没有有向环，有收缩边，则展开收缩边。

来个图还是很有必要的~~~

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<limits.h>
using namespace std;
const int MAXN = 110;
const int MAXM = 10010;

struct Node
{
    int from;
    int to;
    double w;
};
Node Edges[MAXM];

struct Node1
{
    double x;
    double y;
};
Node1 Point[MAXN];

double Dist(Node1 a, Node1 b)
{
    double x = a.x - b.x;
    double y = a.y - b.y;
    return sqrt(x*x+y*y);
}

int pre[MAXN],vis[MAXN],flag[MAXN];
double In[MAXN],sum;

double ZhuLiu(int root,int N,int M)
{
    sum = 0;
    while(true)
    {
        for(int i = 0; i < N; ++i)
            In[i] = INT_MAX;
        for(int i = 0; i < M; ++i)
        {
            int u = Edges[i].from;
            int v = Edges[i].to;
            if(Edges[i].w < In[v] && u != v)
            {
                pre[v] = u;//v为终点，pre[v]存放起点
                In[v] = Edges[i].w;//权值最小的边
            }
        }
        
        for(int i = 0; i < N; ++i)//如果存在除root以外的孤立点，则不存在最小树形图
        {
            if(i == root)
                continue;
            if(In[i] == INT_MAX)
                return -1;
        }
        int CntNode = 0;
        memset(flag,-1,sizeof(flag));
        memset(vis,-1,sizeof(vis));
        In[root] = 0;
        for(int i = 0; i < N; ++i)   //找环,标记每个环
        {
            sum += In[i];
            int v = i;
            while(vis[v]!=i && flag[v]==-1 && v!=root)//每个点寻找其前序点，要么最终寻找至根部，要么找到一个环  
            {
                vis[v] = i;
                v = pre[v];
            }
            if(v != root && flag[v] == -1)  //新图重新编号
            {
                for(int u = pre[v]; u != v; u = pre[u]) 
                    flag[u] = CntNode;
                flag[v] = CntNode++;
            }
        }
        if(CntNode == 0)    //无环，跳出
            break;
        for(int i = 0; i < N; ++i)
        {
            if(flag[i] == -1)
                flag[i] = CntNode++;
        }
        for(int i = 0; i < M; ++i)  //建立新图，更新其他点到环的距离
        {
            int v = Edges[i].to;
            Edges[i].from = flag[Edges[i].from];
            Edges[i].to = flag[Edges[i].to];
            if(Edges[i].from != Edges[i].to)
                Edges[i].w -= In[v];
        }
        N = CntNode;
        root = flag[root];
    }
    return sum;
}

int main()
{
    int x,y,N,M;
    while(~scanf("%d%d",&N,&M))
    {
        int id = 0;
        for(int i = 0; i < N; ++i)
            scanf("%lf%lf",&Point[i].x,&Point[i].y);
        for(int i = 0; i < M; ++i)
        {
            scanf("%d%d",&x,&y);
            if(x == y)
                continue;
            x--;
            y--;
            Edges[id].from = x;
            Edges[id].to = y;
            Edges[id++].w = Dist(Point[x],Point[y]);
        }
        double ans = ZhuLiu(0,N,id);
        if(ans == -1)
            printf("poor snoopy\n");
        else
            printf("%.2lf\n",ans);
    }
    return 0;
}

POJ3164 Command Network【最小树形图】【朱刘算法】