题目大意:给一张没有自环,没有重边的有向图。问最多加多少条边,要求加边完后的图没有自环,没有重边,且不是强连通的。
因为要添加最多的边,因此显然可以得到,最后的图是由两个强连通分量组成,设为a,b。a,b都为完全图,且a中所有点都指向b中每个点,b中点没有指向a中的点。
设a中的点数为x,b中的点数是y。
因此最后添加的边数N = x * (x - 1) + y * (y - 1) + x * y - m
N = (x + y)2 - (x + y) + x * y - m = n2 - n + x * y - m
因此只需要x * y最小即可
而x只能是缩点后入读为0的点
y只能是缩点后出度为0的点
因此枚举即可
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <vector>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const double eps = 1e-6;
const int N = 100010;
int low[N], dfn[N], timestamp;
int stk[N], instk[N], top;
int h[N], e[N], ne[N], idx;
int scc_cnt, s[N], id[N], cd[N], rd[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void init()
{
memset(h, -1, sizeof h);
memset(low, 0, sizeof low);
memset(dfn, 0, sizeof dfn);
timestamp = idx = top = scc_cnt = 0;
memset(instk, 0, sizeof instk);
memset(s, 0, sizeof s);
memset(rd, 0, sizeof rd);
memset(cd, 0, sizeof cd);
}
void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp;
stk[++ top] = u;
instk[u] = 1;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if (instk[j]) low[u] = min(low[u], dfn[j]);
}
if (dfn[u] == low[u])
{
int y;
++ scc_cnt;
do{
y = stk[top --];
instk[y] = 0;
id[y] = scc_cnt;
s[scc_cnt] ++;
}while(y != u);
}
}
int main()
{
int T;
cin >> T;
for (int mm = 1; mm <= T; mm ++)
{
printf("Case %d: ", mm);
init();
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i ++)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
for (int i = 1; i <= n; i ++)
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= n; i ++)
for (int j = h[i]; ~j; j = ne[j])
{
int a = id[i], b = id[e[j]];
if (a != b)
cd[a] ++, rd[b] --;
}
if (scc_cnt == 1)
{
cout << -1 << endl;
continue;
}
LL res = -1;
for (int i = 1; i <= scc_cnt; i ++)
{
LL ans = n * n - n;
if (cd[i] == 0 || rd[i] == 0)
res = max(res, ans - s[i] * (n - s[i]) - m);
}
cout << res << endl;
}
return 0;
}