Redundant Paths 分离的路径

题目描述

为了从F(1≤F≤5000)个草场中的一个走到另一个，贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树．奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择．
每对草场之间已经有至少一条路径．给出所有R(F-1≤R≤10000)条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量,
路径由若干道路首尾相连而成．两条路径相互分离，是指两条路径没有一条重合的道路．但是，两条分离的路径上可以有一些相同的草场．
对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路．

输入格式

第1行输入F和R，接下来R行，每行输入两个整数，表示两个草场，它们之间有一条道路．

输出格式

最少的需要新建的道路数．

首先我们容易得出一个结论，环上任意两点都有两条分离路径

然后我们如果将这个图缩点后将会得到一个新图，（先缩点为敬）

我们需要添加路径使变成边双连通图，边双连通图上每一条边都一定在一个环内，我们让每两个叶子节点连边使它构成环就行了。

那么问题就变成了求叶子节点个数。

然后如果叶子数为奇数我们需要再将这个点与任意一个点相连。（叶子+1）/2就完了

如果为偶数直接就是（叶子）/2

#include<bits/stdc++.h>

#define ll long long

#define A 2000000

#define read(a) scanf("%lld",&a)

#define put(a) printf("%lld\n",a)

using namespace std;

map<pair<ll,ll>,bool> mp;

ll low[A],size[A],dfn[A],head[A],ver[A],nxt[A],cut[A],ans[A],sz[A];

ll ver2[A],nxt2[A],head2[A],out[A],belong[A],sta[A],ru[A],sb=0;

string s;

bool ins[A],flag[A],via[A];

vector<ll> scc[A];

ll n,m,num=0,root,top=0,tot=0,tot2=0,sum=0,cnt=0;

void add2(ll x,ll y){

    ver2[++tot2]=y;nxt2[tot2]=head2[x];head2[x]=tot2;out[x]++;ru[y]++;return ;

}

void add(ll x,ll y){

    ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;return ;

}

inline void rebuilt(){

    for(ll i=1;i<=n;i++){

        for(ll j=head[i];j;j=nxt[j]){

            ll y=ver[j];

            if(y!=i)

            if(belong[i]!=belong[y]/*&&*/)

                add2(belong[i],belong[y])/*,,,printf("belong i=%lld,belong y=%lld\n",belong[i],belong[y])*/;

        }

    }

}

void tarjan(ll x,ll pre){

    low[x]=dfn[x]=++num;

    sta[++top]=x;ins[x]=1;

    for(ll i=head[x];i;i=nxt[i]){

        ll y=ver[i];

        if(y==pre) continue;

        if(!dfn[y]){

            tarjan(y,x);

            low[x]=min(low[x],low[y]);

        }

        else if(ins[y]){

            low[x]=min(low[x],dfn[y]);

        }

    }

    if(dfn[x]==low[x]){

        ++cnt;ll yy=0;

        while(1){

            yy=sta[top--];

            ins[yy]=0;

            belong[yy]=cnt;

            sz[cnt]++;

            scc[cnt].push_back(yy);

            if(yy==x) break;

        }

    }

}

void shuchu()

{

        for(ll i=1;i<=cnt;i++)

        {

//            printf("第%lld个scc  size=%lld\n",i,sz[i]);

            for(ll j=0;j<scc[i].size();j++)

            {

                cout<<scc[i][j]<<" ";

            }

            cout<<endl;

        }

}

void dfs(ll x){

    flag[x]=1;if(ru[x]==1) sb++;

    for(ll i=head2[x];i;i=nxt2[i]){

        ll y=ver2[i];//        printf("x=%lld y=%lld outx=%lld\n",x,y,out[x]);

        if(flag[y]) continue;

        dfs(y);

    }

}

int main(){

        read(n);read(m);

        for(ll i=1;i<=m;i++){

            ll xx,yy;read(xx),read(yy);

            if(!mp[make_pair(xx,yy)]&&!mp[make_pair(yy,xx)])

            {

                add(xx,yy);add(yy,xx);mp[make_pair(xx,yy)]=1,mp[make_pair(yy,xx)]=1;

            }

        }

        for(ll i=1;i<=n;i++)

            if(!dfn[i])root=i,tarjan(i,0);

        rebuilt();

//        shuchu();

        for(ll i=1;i<=cnt;i++)

        {

//            printf("ru%lld=%lld\n",i,ru[i]);

            if(ru[i]==1) sb++;

        }

        cout<<(sb+1)/2<<endl;

}

巴特西

Redundant Paths 分离的路径

Redundant Paths 分离的路径

题目描述

输入格式

输出格式

最新文章

热门文章