HDU 4635

http://acm.hdu.edu.cn/showproblem.php?pid=4635

问：最多加多少条边，使得原图不是强连通图

正向考虑有困难，不妨反向思考，既最少去掉几条边使得原图不是强连通。

总边数sum=n*(n-1)时肯定是强连通，已经给了m条边，sum-=m

这时把已经强连通的部分进行缩点，对于缩好的点我们把他们分成两部分，保证其中一部分到另一部分没有边（这两部分不强连通），再把sum减去两部分能构成所有的边数，取最大值即为答案

具体做时枚举每个小强连通块，找到num[i]*(n-num[i])最小的情况（num[i]为小强连通块点数），其中必须出度或入度为0的连通块才可以被选择

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <queue>

#include <map>

using namespace std ;

const int INF=0xfffffff ;

struct node

{

    int s,t,nxt ;

}e[] ;

int n,m,idx,ans,tp,cnt,num[],IN[],OUT[],dfn[],vis[],low[],head[],st[],belong[] ;

void add(int s,int t)

{

    e[cnt].s=s ;

    e[cnt].t=t ;

    e[cnt].nxt=head[s] ;

    head[s]=cnt++ ;

}

void tarjan(int u)

{

    dfn[u]=low[u]=++idx ;

    vis[u]= ;

    st[++tp]=u ;

    int v ;

    for(int i=head[u] ;i!=- ;i=e[i].nxt)

    {

        v=e[i].t ;

        if(!dfn[v])

        {

            tarjan(v) ;

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

        }

        else if(vis[v])

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

    }

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

    {

        ans++ ;

        while()

        {

            v=st[tp--] ;

            vis[v]= ;

            belong[v]=ans ;

            num[ans]++ ;

            if(v==u)break ;

        }

    }

}

void sc()

{

    memset(vis,,sizeof(vis)) ;

    memset(dfn,,sizeof(dfn)) ;

    memset(num,,sizeof(num)) ;

    idx=tp=ans= ;

    for(int i= ;i<=n ;i++)

        if(!dfn[i])

            tarjan(i) ;

}

int main()

{

    int T ;

    scanf("%d",&T) ;

    for(int cas= ;cas<=T ;cas++)

    {

        cnt= ;

        memset(head,-,sizeof(head)) ;

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

        for(int i= ;i<m ;i++)

        {

            int s,t ;

            scanf("%d%d",&s,&t) ;

            add(s,t) ;

        }

        sc() ;

        if(ans==)

        {

            printf("Case %d: -1\n",cas) ;

            continue ;

        }

        memset(IN,,sizeof(IN)) ;

        memset(OUT,,sizeof(OUT)) ;

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

        {

            for(int i=head[u] ;i!=- ;i=e[i].nxt)

            {

                int tt=e[i].t ;

                if(belong[tt]==belong[u])continue ;

                IN[belong[tt]]++ ;

                OUT[belong[u]]++ ;

            }

        }

        int ret=- ;

        for(int i= ;i<=ans ;i++)

        {

            if(!IN[i] || !OUT[i])

                ret=max(ret,n*(n-)-m-num[i]*(n-num[i])) ;

        }

        printf("Case %d: %d\n",cas,ret) ;

    }

    return  ;

}

巴特西

HDU 4635

最新文章

热门文章