HDU 4635 Strongly connected(shrink nodes)

Description

给出一个含有N个点M条有向边的简单图(无自环无重边)，求：在保证图是简单图且非强连通的前提下，最多可以再添加几条边？

Analyze

1.现在有N个点，0条边，可添加 N * (N - 1) 条边(保证是简单图)

2.为了保证非强连通，需要去掉一些边。最终的图环缩点后是两个大点。假设第一个大点中含有X个小点，那第二个大点中就含有(N - X)个小点，那原先他们之间的2 * X*(N-X)条边就要去掉一半，即答案是N(N - 1) - X(N - X)

3.由于原图已有M条边，所以最终答案是N(N - 1) - M - X(N - X)

4.那么X(N - X)在什么情况下最小呢？当二次函数处理时发现X越近0或越近N时最小，即最后的两个大点所含的小点数目之差越大越优。

5.假设原图缩点后各大点所含小点数为：2，4，8，16。那么将2做一强连通分量，剩下的4+8+16做另一强连通分量时，答案最优。所以要找缩点后内部含点数最少的强连通分量，其内部点数为X。

6.有个前提：这个强联通分量的入度或出度为0(才可以成为最后两个点之一)

Code

#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100100;
const int M = 2000100;
const int INF = 0x3f3f3f3f;
#define ll long long

ll n, m;

int head[N], cnt;
struct edge
{
    int u, v, pre;
}e[M];

void add(int u, int v)
{
    e[cnt].u = u;
    e[cnt].v = v;
    e[cnt].pre = head[u];
    head[u] = cnt++;
}

stack<int> st;
bool inst[N];
int low[N], times[N], t, num, ltt[N];
ll nodes[N];
void Tarjan(int x)
{
    st.push(x);
    inst[x] = 1;
    low[x] = times[x] = ++t;
    for(int i = head[x]; ~i; i = e[i].pre)
    {
        int to = e[i].v;
        if(!times[to])
        {
            Tarjan(to);
            low[x] = min(low[x], low[to]);
        }
        else if(inst[to])
            low[x] = min(low[x], times[to]);
    }

    if(low[x] == times[x])
    {
        num++;
        while(!st.empty())
        {
            int tem = st.top();
            st.pop();
            ltt[tem] = num;
            nodes[num]++;
            inst[tem] = 0;
            if(tem == x)
                break;
        }
    }
}

int in[N], out[N];

void init()
{
    cnt = t = num = 0;
    while(!st.empty())
        st.pop();
    memset(in, 0, sizeof(in));
    memset(out, 0, sizeof(out));
    memset(low, 0, sizeof(low));
    memset(ltt, 0, sizeof(ltt));
    memset(inst, 0, sizeof(inst));
    memset(head, -1, sizeof(head));
    memset(nodes, 0, sizeof(nodes));
    memset(times, 0, sizeof(times));
}

int main()
{
    int _, p = 1;
    scanf("%d", &_);
    while(_--)
    {
        scanf("%lld %lld", &n, &m);

        init();

        int u, v;
        for(int i = 0; i < m; ++i)
        {
            scanf("%d %d", &u, &v);
            add(u, v);
        }

        for(int i = 1; i <= n; ++i)
            if(!times[i])
                Tarjan(i);

        if(num == 1)
        {
            printf("Case %d: -1\n",p++);
            continue;
        }

        for(int i = 0; i < cnt; ++i)
        {
            u = ltt[ e[i].u ], v = ltt[ e[i].v ];
            if(u != v)
                in[v]++, out[u]++;
        }

        ll mmin = n;
        for(int i = 1; i <= num; ++i)
            if(in[i] == 0 || out[i] == 0)
                mmin = min(mmin, nodes[i]);
        printf("Case %d: ",p++);
        cout << n * (n - 1) - m - mmin * (n - mmin) << '\n';
    }
    return 0;
}

Something

1.数组很多时，不要漏掉任意一个的初始化。

2.超过1个int数字的加减乘除(尤其乘法)记得用long long。

眼瞎写错下标Debug2小时

for(int i = 0; i < cnt; ++i)
{
    u = ltt[ e[cnt].u ], v = ltt[ e[cnt].v ];
    if(u != v)
        in[v]++, out[u]++;
}

眼瞎的痛