hdu4635 有向图最多添加多少边使图仍非强连通

思路：先缩点成有向无环图，则必然含有出度为0的点/入度为0的点，因为要使添加的边尽量多，最多最多也就n*（n-1）条减去原来的m条边，这样是一个强连通图，问题转化为最少去掉几条，使图不强连通，原来图中入度的点，若不添加入度，则必然不连通，同理出度为0的也一样，所以，找入度/出度为0的点中， ki(n-ki)最小的，这里KI是缩点后该SCC中的点数量，这个结果就是最小去掉的边数了。

思路清晰，1A。

#include<iostream>

#include<vector>

#include<cstdio>

#include<cstring>

#include<stack>

using namespace std;

int n,m;

const int maxv=100030;

vector<vector<int> >edges(maxv);

int visited[maxv]; int low[maxv];   int dfn[maxv];

int ind[maxv];     int outd[maxv];  int sccnum[maxv];

int scc[maxv];

int num;int times;

stack<int>s;

int instack[maxv];

void tarjan(int u)

{

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

    instack[u]=1;

    s.push(u);

    int len=edges[u].size();

    for(int i=0;i<len;i++)

    {

        int v=edges[u][i];

        if(visited[v]==0)

        {

             visited[v]=1;

               tarjan(v);

            if(low[u]>low[v])low[u]=low[v];

        }

        else if(instack[v]&&low[u]>dfn[v])

        {

            low[u]=dfn[v];

        }

    }

    if(dfn[u]==low[u])         //在一个SCC

    {

        num++;int temp;int snum=0;

         do

        {

            snum++;

             temp=s.top();

             instack[temp]=0;

            s.pop();

            scc[temp]=num;

        } while(temp!=u);

        sccnum[num]=snum;

    }

}

void readin()            //读入数据

{

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

    int a,b;

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

    {

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

        edges[a].push_back(b);

    }

}

void initialize()

{

    num=times=0;

    for(int i=0;i<=100000;i++)

    {

        dfn[i]=low[i]=ind[i]=outd[i]=visited[i]=sccnum[i]=scc[i]=0;

        edges[i].clear();

    }

}

int solve()

{

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

       if(visited[i]==0)

        {

            visited[i]=1;

            tarjan(i);

        }

    if(num==1){return -1;}

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

   {

       int len=edges[i].size();

       for(int j=0;j<len;j++)

       {

          int v=edges[i][j];

          if(scc[v]!=scc[i])

          {

            outd[scc[i]]++;

            ind[scc[v]]++;

          }

       }

    }

    int mincut=1000000000;

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

    {

       int temp=0;

       if(outd[i]==0||ind[i]==0)

       {

           temp=sccnum[i]*(n-sccnum[i]);

           if(temp<mincut)mincut=temp;

       }

    }

    return n*(n-1)-m-mincut;

}

int main()

{

    int T;

    cin>>T;int cases=1;

    while(T--)

    {

        initialize();

       readin();

      int ans=solve();

     printf("Case %d: %d\n",cases++,ans);

    }

   return 0;

}

巴特西

hdu4635 有向图最多添加多少边使图仍非强连通

最新文章

热门文章