hdu 4635 Strongly connected(Tarjan)

做完后，看了解题报告，思路是一样的。我就直接粘过来吧

最终添加完边的图，肯定可以分成两个部X和Y，其中只有X到Y的边没有Y到X的边，那么要使得边数尽可能的多，则X部肯定是一个完全图，Y部也是，同时X部中每个点到Y部的每个点都有一条边，假设X部有x个点，Y部有y个点，有x+y=n，同时边数F=x*y+x*(x-1)+y*(y-1)，整理得：F=N*N-N-x*y，当x+y为定值时，二者越接近，x*y越大，所以要使得边数最多，那么X部和Y部的点数的个数差距就要越大，所以首先对于给定的有向图缩点，对于缩点后的每个点，如果它的出度或者入度为0，那么它才有可能成为X部或者Y部，所以只要求缩点之后的出度或者入度为0的点中，包含节点数最少的那个点，令它为一个部，其它所有点加起来做另一个部，就可以得到最多边数的图了

//109MS 	2916KB
#include <stdio.h>
#include <string.h>
#define LL long long
const int M = 100005;
const int inf = 0x3f3f3f3f;
struct Edge
{
    int to,nxt;
} edge[M];

int head[M],low[M],dfn[M],stack[M+10];
int vis[M],out[M],in[M],belong[M];
int scc,cnt ,top,ep;
LL n,m;
int min (int a,int b)
{
    return a > b ? b : a;
}
void addedge (int cu,int cv)
{
    edge[ep].to = cv;
    edge[ep].nxt = head[cu];
    head[cu] = ep ++;
}

void Tarjan(int u)
{
    int v;
    dfn[u] = low[u] = ++cnt;
    stack[top++] = u;
    vis[u] = 1;
    for (int i = head[u]; i != -1; i = edge[i].nxt)
    {
        v = edge[i].to;
        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])
    {
        ++scc;
        do
        {
            v = stack[--top];
            vis[v] = 0;
            belong[v] = scc;
        }
        while (u != v);
    }
}

void solve()
{
    int u,v;
    scc = top = cnt = 0;
    memset (vis,0,sizeof(vis));
    memset (dfn,0,sizeof(dfn));
    memset (out,0,sizeof(out));
    memset (in,0,sizeof(in));
    for (u = 1; u <= n; u ++)
        if (!dfn[u])
            Tarjan(u);

    for (u = 1; u <= n; u ++)
    {
        for (int i = head[u]; i != -1; i =edge[i].nxt)
        {
            v = edge[i].to;
            if (belong[u] != belong[v])
            {
                out[belong[u]] ++;
                in[belong[v]] ++;
            }
        }
    }
    int num[M],Min;
    memset (num,0,sizeof(num));
    for (u = 1; u <= n; u ++)
        if (!in[belong[u]]) num[belong[u]] ++;
    for (u = 1; u <= scc; u ++)
        if (num[u]!= 0&&num[u]<Min)
            Min = num[u];

    memset (num,0,sizeof(num));
    for (u = 1; u <= n; u ++)
        if (!out[belong[u]]) num[belong[u]] ++;
    for (u = 1; u <= scc; u ++)
        if (num[u]!= 0&&num[u]<Min)
            Min = num[u];
    if (scc == 1)
    {
        printf ("-1\n");
        return ;
    }
    LL ans = n*(n-1)-Min*(n-Min) - m;
    printf ("%I64d\n",ans);
}
int main ()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    int T,u,v,cnt = 0;
    scanf ("%d",&T);
    while (T --)
    {
        scanf ("%I64d%I64d",&n,&m);
        ep = 0;
        memset (head,-1,sizeof(head));
        for (int i = 0; i < m; i++)
        {
            scanf ("%d%d",&u,&v);
            addedge(u,v);
        }
        printf ("Case %d: ",++cnt);
        solve();
    }
    return 0;
}

补充：软件开发 , C++ ,

上一个：[leetcode]Pow(x, n)
下一个：hdu 4612 Warm up