P2860 [USACO06JAN]冗余路径Redundant Paths

题目描述

为了从F(1≤F≤5000)个草场中的一个走到另一个，贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树．奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择．

每对草场之间已经有至少一条路径．给出所有R(F-1≤R≤10000)条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量, 路径由若干道路首尾相连而成．两条路径相互分离，是指两条路径没有一条重合的道路．但是，两条分离的路径上可以有一些相同的草场．对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路．

输入输出格式

输入格式：

Line 1: Two space-separated integers: F and R

Lines 2..R+1: Each line contains two space-separated integers which are the fields at the endpoints of some path.

输出格式：

Line 1: A single integer that is the number of new paths that must be built.

其实题目并不难，但我想太复杂了，各种仙人掌仙人掌的。。

我们考虑如果一对点合法，一定是它们的路径上有环，如果所有的点对都合法，那么每个点至少在一个环上。

然而这样并不充分。

考虑它在什么时候是充分的。

我们可以先把原有的环缩掉，因为原有的环中的所有点都等价

好了，现在有一颗树，我们再探讨一下充分吗，经过充分的模拟，我们发现这是充分的

如何令树上所有的点都在环上呢？

我们两两连接叶子节点

此题需要判重边

Code：

#include <cstdio>

#include <cstring>

#include <map>

using namespace std;

int min(int x,int y){return x<y?x:y;}

const int N=5010;

int head[N],Next[N<<2],to[N<<2],cnt;

void add(int u,int v)

{

    to[++cnt]=v;Next[cnt]=head[u];head[u]=cnt;

}

int dfn[N],low[N],s[N],in[N],is[N],ha[N],tot,dfs_clock;

int ans,cnt0,n,m,n0;

void tarjan(int now,int fa)

{

    dfn[now]=low[now]=++dfs_clock;

    s[++tot]=now;in[now]=1;

    for(int i=head[now];i;i=Next[i])

    {

        int v=to[i];

        if(v==fa) continue;

        if(!dfn[v])

        {

            tarjan(v,now);

            low[now]=min(low[now],low[v]);

        }

        else if(in[v])

            low[now]=min(low[now],dfn[v]);

    }

    if(low[now]==dfn[now])

    {

        int k;n0++;

        do

        {

            k=s[tot--];

            ha[k]=n0;

            in[k]=0;

        }while(k!=now);

    }

}

map <int,map <int,int> > used;

int main()

{

    scanf("%d%d",&n,&m);

    for(int u,v,i=1;i<=m;i++)

    {

        scanf("%d%d",&u,&v);

        if(used[u][v]) continue;

        used[u][v]=used[v][u]=1;

        add(u,v),add(v,u);

    }

    tarjan(1,0);

    memset(in,0,sizeof(in));

    for(int u=1;u<=n;u++)

        for(int i=head[u];i;i=Next[i])

            if(ha[u]!=ha[to[i]])

                in[ha[u]]++;

    for(int i=1;i<=n0;i++)

        if(in[i]==1) ans++;

    printf("%d\n",ans+1>>1);

    return 0;

}

2018.8.8

巴特西

洛谷 P2860 [USACO06JAN]冗余路径Redundant Paths 解题报告

P2860 [USACO06JAN]冗余路径Redundant Paths

题目描述

输入输出格式

输入格式：

输出格式：

最新文章

热门文章