题意：给出一个图，如果这个图一开始就不是强连通图，求出最多加多少条边使这个图还能保持非强连通图的性质。
思路：不难想到缩点转化为完全图，然后找把它变成非强连通图需要去掉多少条边，但是应该怎么处理呢……有人给出这样的答案，找到分量中点数最少的块，把它的所有入边都去掉……好像是对的，但是万一这个块本来就有一个入度怎么办？这个边是不可以删的啊。所以我觉得这种办法是有点的问题的，所以最靠谱的方法还是斌哥他们给出的方法，最后的时候把点分成两个集合x和y，x和y本身都是完全图块，然后让x中的每一个点都指向y中的每一个点，y中没有边指向x，假设x中有a个点，y中有b个点，a+b = n，容易得到ans = a*(a-1) + b*(b-1) - a*b - m,等价变形为ans = n*n - n - a*b - m,根据我们高中学过的不等式的性质，a×b在a=b的时候取得最大值，a与b相差的越多，a×b越小，所以我们可以让a更小，所以可以选择一个入度或者出度为0的分量作为x，选出点最少的块作为x，那么ans就是最大的。
感悟：感觉这个题很好的把图论和数学划分的思想结合到了一起。
#include<iostream> #include<cstdio> #include<cstring> #include<stack> using namespace std; #define maxn 100010 int dfn[maxn],low[maxn],id[maxn],sum[maxn],in[maxn],out[maxn]; int head[maxn],all,tot,scc,vis[maxn]; struct Edge { int to,nxt; }edge[maxn]; stack<int> st; void init() { memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(id,0,sizeof(id)); memset(sum,0,sizeof(sum)); all = 0; scc = 0; while(!st.empty()) st.pop(); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); } void tarjan(int u) { dfn[u] = low[u] = ++all; st.push(u); for(int i = head[u];i != -1;i = edge[i].nxt) { int v = edge[i].to; if(!dfn[v]) { tarjan(v); low[u] = min(low[u],low[v]); } else if(!id[v]) low[u] = min(low[u],dfn[v]); } if(low[u] == dfn[u]) { int num; scc++; while(!st.empty()) { num = st.top(); st.pop(); id[num] = scc; sum[scc]++; if(num == u) break; } } } int main() { int t,n,m,a,b,ca = 0 ; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); tot = 0; memset(head,-1,sizeof(head)); for(int i = 0;i < m;i++) { scanf("%d%d",&a,&b); edge[i].to = b; edge[i].nxt = head[a]; head[a] = i; } init(); for(int i = 1;i <= n;i++) { if(!dfn[i]) tarjan(i); } printf("Case %d: ",++ca); if(scc == 1) { puts("-1"); continue; } for(int u = 1;u <= n;u++) { for(int i = head[u];i != -1;i = edge[i].nxt) { int v = edge[i].to; if(id[u] != id[v]) { in[id[v]]++; out[id[u]]++; } } } long long tmpans = (long long)(n*n-n-m); long long ans = 0; for(int i = 1;i <= scc;i++) { if(in[i]==0 || out[i]==0) ans = max(ans,tmpans - sum[i]*(n-sum[i])); } printf("%I64d ",ans); } return 0; }