POJ3177-Redundant Paths

[POJ] [INDEX] [3177] [Redundant Paths]

[Time: 1000MS] [Memory: 65536K] [难度: 中级] [分类: 连通分量/割边/割点]

---

问题描述

为了保护放牧环境，避免牲畜过度啃咬同一个地方的草皮，牧场主决定利用不断迁移牲畜进行喂养的方法去保护牧草。然而牲畜在迁移过程中也会啃食路上的牧草，所以如果每次迁移都用同一条道路，那么该条道路同样会被啃咬过度而遭受破坏。

现在牧场主拥有F个农场，已知这些农场至少有一条路径连接起来（不一定是直接相连），但从某些农场去另外一些农场，至少有一条路可通行。为了保护道路上的牧草，农场主希望再建造若干条道路，使得每次迁移牲畜时，至少有2种迁移途径，避免重复走上次迁移的道路。已知当前有的R条道路，问农场主至少要新建造几条道路，才能满足要求？

解题思路

“使得每次迁移牲畜时，至少有2种迁移途径，避免重复走上次迁移的道路。”就是说当吧F个农场看作点、路看作边构造一个无向图G时，图G不存在桥。

那么可以建立模型：

给定一个连通的无向图G，至少要添加几条边，才能使其变为双连通图。

这题是和 POJ3352 一模一样的题，只不过表述方式不同而已。

详细解题过程请参考我 POJ3352 的解题报告，有详细叙述。

看完 POJ3352 的解题报告，再回来看看本题要注意的一些地方：

本题和 POJ3352 最大的区别就是， POJ3352 保证了没有重边，而本题有重边。

而 POJ3352 的解题报告已经说过，当两点之间出现重边时，就不可以利用Low值去划分【边双连通分量】了，因为此时不同Low值的两点可能属于同一个【边双连通分量】！

那么如何解决重边的问题？

• 1、 构造图G时把重边也考虑进来，然后在划分边双连通分量时先把桥删去，再划分，其中桥的一端的割点归入当前正在划分的边双连通分量。这个处理比较麻烦；
• 2、 在输入图G的边时，若出现重边，则不把重边放入图G，然后在划分边双连通分量时依然用Low划分。

两者相权，当然是第2种方法更好处理了。

其实用邻接矩阵去存储图G的同学，是无需考虑重边的问题的。

但是用邻接链表去存储图G的同学就不得不考虑了，因为基本上都是用头插入法在链表中插入边的，所以无法检测重边。而改用尾插入法，则可以在指针从链头移到链尾的同时，顺便加一个判断，出现重边则不再插入，否则插入到尾部。

测试数据

• 输入：input
• 输出：output

AC 源码

//236K   16MS  

#include<iostream>
using namespace std;

class Node
{
public:
    int id;
    class Node* next;
    Node():id(0),next(0){}
};

class solve
{
public:
    solve(int f,int r):F(f),R(r)
    {
        Initial();          
        Input_Creat();
        Tarjan(1,-1);       //本题给定的图G为连通的，因此从任意节点开始搜索均可
        printf("%d\n",BCC_SP_D_E());
    }
    ~solve()
    {
        delete[] DFN;
        delete[] Low;
        delete[] degree;

        EmptyList();
    }

    int min(int a,int b) const{return a<b?a:b;}

    void Initial(void);             //申请存储空间并初始化
    void Input_Creat(void);         //输入并创建图G
    void AddEdge(int a,int b);      //向链表插入边a<->b (尾插入法，避免重边)

    void Tarjan(int s,int father);  //计算Low[]数组，用于寻找所有边双连通分量
    int BCC_SP_D_E(void);           //把每个边双连通分量(BCC)构造为缩点(SP)，并计算每个缩点的度数(D)
                                    //返回值为使得图G为双连通所需添加的最少的边(E)的数量

    void DelLink(Node* p);          //释放以p为表头的整条链
    void EmptyList(void);           //释放邻接链表

protected:

    int F;                  //the number of islands
    int R;                  //the number of roads
    Node** LinkHead;        //邻接链表表头

    int TimeStamp;          //(外部)时间戳
    int* DFN;               //DFN[u]: 结点u的搜索次序(时间戳)
    int* Low;               //Low[u]: 结点u或u的子树能够追溯到的最早的栈中结点的次序号

    int* degree;            //记录每个缩点的总度数
};

void solve::Initial(void)
{
    LinkHead=new Node*[F+1];
    for(int i=1;i<=F;i++)
        LinkHead[i]=0;

    TimeStamp=0;
    DFN=new int[F+1];
    Low=new int[F+1];
    memset(DFN,0,sizeof(int)*(F+1));
    memset(Low,0,sizeof(int)*(F+1));

    degree=new int[F+1];
    memset(degree,0,sizeof(int)*(F+1));

    return;
}

void solve::Input_Creat(void)
{
    int a,b;
    Node* tmp;
    for(int j=1;j<=R;j++)
    {
        scanf("%d %d",&a,&b);

        if(!LinkHead[a])
            LinkHead[a]=new Node;
        if(!LinkHead[b])
            LinkHead[b]=new Node;

        AddEdge(a,b);
    }
    return;
}

void solve::AddEdge(int a,int b)
{
    Node* pa=LinkHead[a];
    Node* p1=new Node;
    p1->id=b;

    while(pa->next)
    {
        pa=pa->next;
        if(pa->id==p1->id)  //出现重边，重边不插入链表
            return;
    }
    pa->next=p1;

    Node* pb=LinkHead[b];
    Node* p2=new Node;
    p2->id=a;

    while(pb->next)         //能执行到这里说明a<->b不是重边
        pb=pb->next;        //直接搜索到链表尾部插入
    pb->next=p2;

    return;
}

void solve::Tarjan(int s,int father)
{
    DFN[s]=Low[s]=++TimeStamp;
    for(Node* p=LinkHead[s]->next;p;p=p->next)
    {
        int t=p->id;
        if(t!=father && DFN[t]<DFN[s])
        {
            if(DFN[t]==0)           //s->t为树枝边
            {
                Tarjan(t,s);
                Low[s]=min(Low[s],Low[t]);
            }
            else                    //s->t为后向边
            {
                Low[s]=min(Low[s],DFN[t]);
            }
        }
    }
    return;
}

int solve::BCC_SP_D_E(void)
{
    for(int i=1;i<=F;i++)
        if(LinkHead[i])
        {
            for(Node* p=LinkHead[i]->next;p;p=p->next)  //枚举图G中每两个连通的点i<->j
            {                                           //由于图G为无向图，则连通是双向的
                int j=p->id;
                if(Low[i]!=Low[j])      //图G中Low值相同的两个点必定在同一个边双连通分量(即同一个缩点)中
                {                       //检查i、j是否不在同一个缩点中

                    degree[Low[i]]++;   //结点i所在的缩点的度+1
                    degree[Low[j]]++;   //结点j所在的缩点的度+1
                }
            }
        }

    int leave=0;            //记录总度数=1（叶子）的缩点
    for(int k=1;k<=F;k++)   //枚举各个缩点的度数D
        if(degree[k]/2==1)  //由于是无向图，因此每个缩点的度都重复计算了2次，除2后才是真实的度数
            leave++;

    return (leave+1)/2;     //将一棵树连成一个边双连通分量至少需要添加的边数=(叶子节点数+1)/2
}

void solve::DelLink(Node* p)
{
    if(p->next)
        p=p->next;
    delete[] p;
    return;
}

void solve::EmptyList(void)
{
    for(int i=1;i<=F;i++)
        if(LinkHead[i])
            DelLink(LinkHead[i]);
    return;
}

int main(void)
{
    int f,r;
    while(scanf("%d %d",&f,&r)!=EOF)
        solve poj3177(f,r);

    return 0;
}

---

版权声明

　　

• Site: http://exp-blog.com
• Mail: [email protected]

---