M_sea

洛谷1656 炸铁路
题目描述因为某国被某红色政权残酷的高压暴力统治。美国派出将军uim,对该国进行战略性措施,以解救涂炭的生灵。该国有...
扫描右侧二维码阅读全文
22
2017/09

洛谷1656 炸铁路

题目描述

因为某国被某红色政权残酷的高压暴力统治。美国派出将军uim,对该国进行战略性措施,以解救涂炭的生灵。

该国有n个城市,这些城市以铁路相连。任意两个城市都可以通过铁路直接或者间接到达。

uim发现有些铁路被毁坏之后,某两个城市无法互相通过铁路到达。这样的铁路就被称为key road。

uim为了尽快使该国的物流系统瘫痪,希炸毁铁路,已达到存在某两个城市无法互相通过铁路到达的效果。

然而,只有一发炮弹(美国国会不给钱了)。所以,他能轰炸那一条铁路呢?
传送门

算法

枚举+联通

先枚举断掉的边,然后判断整个图是否联通即可。

至于判联通,并查集/Dijkstra/Kruskal/Prim……皆可

Tarjan

我们把题目抽象一下:有n个点,m条边,求出所有没有后就会是原图“分裂”的边。
用专业术语来说,就是求桥(或割边)。

关于Tarjan可以去看我以前的文章
在这里,一条边(u,v)是桥当且仅当dfn[u]<low[v]。
所以这题用Tarjan就可以了,(还是道模板题)

一些补充

这道题的输出要按大小排序,用STL中的pair即可(因为pair已经定义了<)。
而且每条输出的边(u,v)要保证u<v。

代码

枚举+并查集

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define mp make_pair
using namespace std;
struct Edge //边
{
    int x,y;
    Edge() { this->x=this->y=0; }
}e[5010];
int root[200]; //并查集
pair<int,int> answ[5010]; //答案
int n,m;
inline int find(int k) //并查集查找根节点
{
    if (root[k]!=k) root[k]=find(root[k]);
    return root[k];
}
inline void merge(int x,int y) //合并
{
    int r1=find(x),r2=find(y);
    if (r1!=r2) root[r2]=r1;
}
inline void Init() { for (int i=1;i<=n;i++) root[i]=i; } //并查集的初始化
int main()
{
    scanf("%d%d",&n,&m);
    int u,v,num=0;
    for (int i=1;i<=m;i++)v//输入+建图
    {
        scanf("%d%d",&u,&v);
        e[i].x=u; e[i].y=v;
    }
    for (int i=1;i<=m;i++) //枚举断边
    {
        Init(); //初始化
        for (int j=1;j<=m;j++)
        {
            if (i==j) continue; //断边不连
            else merge(e[j].x,e[j].y); //合并
        }
        bool is=false;
        for (int j=2;j<=n;j++) 
            if (find(j)!=find(1))  //不在1的集合,也就是图不联通
            {
                is=true;
                break;
            }
        if (is) 
        {
            if (e[i].x<e[i].y) answ[++num]=mp(e[i].x,e[i].y); //存答案,注意u<v
            else answ[++num]=mp(e[i].y,e[i].x);
        }
    }
    sort(answ+1,answ+num+1); //排序
    for (int i=1;i<=num;i++) printf("%d %d\n",answ[i].first,answ[i].second); //输出
    return 0;
}

Tarjan

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define mp make_pair
using namespace std;
int g[200][200]; //邻接矩阵
int dfn[200],low[200];
int dfs_clock,ansnum;
pair<int,int> ans[5010]; //答案
int n,m;
void Tarjan(int k,int fa) //Tarjan
{
    dfn[k]=low[k]=++dfs_clock; //赋初值
    for (int i=1;i<=n;i++)
    {
        if (i==fa||!g[k][i]) continue; //不连通或是其父节点就不行
        if (!dfn[i]) { Tarjan(i,k); low[k]=min(low[k],low[i]); } //未访问过就Tarjan,然后更新low
        low[k]=min(low[k],dfn[i]); //再更新
        if (dfn[k]<low[i]) //是割边
        {
            ansnum++; //存答案
            if (k<i) ans[ansnum]=mp(k,i); //注意顺序
            else ans[ansnum]=mp(i,k);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    int u,v;
    for (int i=1;i<=m;i++) //输入+建图
    {
        scanf("%d%d",&u,&v);
        g[u][v]=g[v][u]=true;
    }
    Tarjan(1,1); sort(ans+1,ans+ansnum+1); //Tarjan+排序
    for (int i=1;i<=ansnum;i++) printf("%d %d\n",ans[i].first,ans[i].second); //输出
    return 0;
}

枚举+并查集

代码待填
最后修改:2018 年 11 月 09 日 04 : 12 PM

发表评论