强连通分量
我们利用强连通分量进行缩点。然后找入度为0或者出度为0的点。
他们其中一个一定是在我们最终的图中被孤立的点。
为什么要这样说呢?
因为你仔细想想啊。假如我没有边,我让你用最多的边连出一个不是强连通分量的图
你是不是孤立一个点,使他只有出度没有入度或者只有入度没有出度?
那,这里不也是一样的吗?!其实,顺着感觉走就可以了。
然后我们统计就可以了。我们想对于一个出度为零或者入度为零的点,孤立他得到的最大收益应该为:
n(n-1)-m-cnt[i](n-cnt[i]) cnt[i]指该连通块中的点的数量。
这里用的是割补法求的,刚开始我想直接求,麻烦得很。。。。。。。。
我们注意到,这个式子里面只有一个变量cnt[i]
设为x把他单独出出来看:x^2-n*x 对称轴为n/2
我们可以直接根据这个式子判断,但是其实我们直接取最小值就好了。
因为有一个点数为k的连通块那么就必定会有一个点数为n-k的连通块。而二者是相等的!
不细心,wa了好多发:(
代码如下:
#include<iostream> #include<algorithm> #include<stack> using namespace std; typedef long long ll; const int max_m = 2e5 + 100; const int max_n = 1e5 + 100; struct edge{ int to, next; }E[max_m]; int head[max_n]; int cnt = 1; void add(int from, int to) { E[cnt].to = to; E[cnt].next = head[from]; head[from] = cnt++; } int cct[max_n]; stack<int> st;int tot = 0; int dfn[max_n], low[max_n]; int col[max_n];int color = 0; void tarjan(int u) { dfn[u] = low[u] = ++tot; st.push(u); for (int i = head[u];i;i = E[i].next) { int v = E[i].to; if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if (col[v] == 0)low[u] = min(low[u], dfn[v]); }if (low[u] != dfn[u])return; ++color; while (st.top() != u) { col[st.top()] = color; st.pop(); ++cct[color]; }col[st.top()] = color; st.pop();++cct[color]; } int in[max_n], out[max_n]; int N, M; int main() { int T;scanf("%d", &T); for (int tcase = 1;tcase <= T;++tcase) { scanf("%d %d", &N, &M); fill(head, head + N + 10, 0);cnt = 1; fill(dfn, dfn + N + 10, 0); fill(col, col + N + 10, 0); fill(cct, cct + N + 10, 0); fill(in, in + N + 10, 0); fill(out, out + N + 10, 0); color = tot = 0; for (int i = 1, u, v;i <= M;++i) { scanf("%d %d", &u, &v); add(u, v); }for (int i = 1;i <= N;++i) if (!dfn[i]) tarjan(i); if (color == 1) { printf("Case %d: -1\n", tcase); continue; }for (int u = 1;u <= N;++u) { for (int i = head[u];i;i = E[i].next) { int v = E[i].to; if (col[v] == col[u])continue; ++in[col[v]];++out[col[u]]; } } ll ans = 0;ll tmp = N; for (int i = 1;i <= color;++i) if (in[i] == 0 || out[i] == 0) tmp = min(tmp, (ll)cct[i]); ans = (ll)N * ((ll)N - 1) - ((ll)N - tmp) * tmp - M; printf("Case %d: %lld\n", tcase, ans); } }