HDU 4635 Strongly connected（强连通分量缩点+数学思想）

　　题意：给出一个图，如果这个图一开始就不是强连通图，求出最多加多少条边使这个图还能保持非强连通图的性质。

　　思路：不难想到缩点转化为完全图，然后找把它变成非强连通图需要去掉多少条边，但是应该怎么处理呢……有人给出这样的答案，找到分量中点数最少的块，把它的所有入边都去掉……好像是对的，但是万一这个块本来就有一个入度怎么办？这个边是不可以删的啊。所以我觉得这种办法是有点的问题的，所以最靠谱的方法还是斌哥他们给出的方法，最后的时候把点分成两个集合x和y，x和y本身都是完全图块，然后让x中的每一个点都指向y中的每一个点，y中没有边指向x，假设x中有a个点，y中有b个点，a+b = n，容易得到ans = a*(a-1) + b*(b-1) - a*b - m,等价变形为ans = n*n - n - a*b - m,根据我们高中学过的不等式的性质，a×b在a=b的时候取得最大值，a与b相差的越多，a×b越小，所以我们可以让a更小，所以可以选择一个入度或者出度为0的分量作为x，选出点最少的块作为x，那么ans就是最大的。

　　感悟：感觉这个题很好的把图论和数学划分的思想结合到了一起。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<stack>

using namespace std;

#define maxn 100010

int dfn[maxn],low[maxn],id[maxn],sum[maxn],in[maxn],out[maxn];

int head[maxn],all,tot,scc,vis[maxn];

struct Edge

{

    int to,nxt;

}edge[maxn];

stack<int> st;

void init()

{

    memset(dfn,,sizeof(dfn));

    memset(low,,sizeof(low));

    memset(id,,sizeof(id));

    memset(sum,,sizeof(sum));

    all = ;

    scc = ;

    while(!st.empty()) st.pop();

    memset(in,,sizeof(in));

    memset(out,,sizeof(out));

}

void tarjan(int u)

{

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

    st.push(u);

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

    {

        int v = edge[i].to;

        if(!dfn[v])

        {

            tarjan(v);

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

        }

        else if(!id[v]) low[u] = min(low[u],dfn[v]);

    }

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

    {

        int num;

        scc++;

        while(!st.empty())

        {

            num = st.top();

            st.pop();

            id[num] = scc;

            sum[scc]++;

            if(num == u) break;

        }

    }

}

int main()

{

    int t,n,m,a,b,ca =  ;

    scanf("%d",&t);

    while(t--)

    {

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

        tot = ;

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

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

        {

            scanf("%d%d",&a,&b);

            edge[i].to = b;

            edge[i].nxt = head[a];

            head[a] = i;

        }

        init();

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

        {

            if(!dfn[i])

                tarjan(i);

        }

        printf("Case %d: ",++ca);

        if(scc == )

        {

            puts("-1");

            continue;

        }

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

        {

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

            {

                int v = edge[i].to;

                if(id[u] != id[v])

                {

                    in[id[v]]++;

                    out[id[u]]++;

                }

            }

        }

        long long tmpans = (long long)(n*n-n-m);

        long long ans = ;

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

        {

            if(in[i]== || out[i]==)

                ans = max(ans,tmpans - sum[i]*(n-sum[i]));

        }

        printf("%I64d\n",ans);

    }

    return ;

}

巴特西

HDU 4635 Strongly connected（强连通分量缩点+数学思想）

最新文章

热门文章