翻到E（HDU 4635 Strongly connected）题，这么短的题目，肯定要先看啦。然后D（LightOJ 1229），然后C（ZOJ 2243），然后F(HDU 4711),然后B（CodeForces 385D），然后看A（HDU 3889）好吧，我承认，A题看了一眼就不看了，B题一看是线段什么有点几何的味道就果断放弃，然后C题，傻傻的理解错题意，提交一直WA，然后没办法，看E题，![AV5W2LR]H5YAQXT}1N2LPDY](/d/file/p/2024/07/16/4ae7417454c0cd99b8ea42ab6f27160b.gif "AV5W2LR]H5YAQXT}1N2LPDY")
想到只要保证最后至少两个连通分量，就可以满足题意，然后要求最大值，那就保证有且仅有两个连通分量就可以了，对于一个连通分量最多只能有x(x-1)边, x表示顶点数 ，然后得出一个式子，边数f = n*n-n-1+x*x-(n+1)x;当x更(n+1)/2的差值越大，f越大，换句话说，只要把一个连通分量顶点个数最小的独立出来，把其它的连通分量都合并成一个连通分量就可以了，
view code#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <algorithm>#include <cmath>#include <vector>#include <map>#include <stack>using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;const int N = 100010;int _, cas=1, n, m;int in[N], out[N], num[N];vector<int > G[N];int pre[N], lowlink[N], dfs_clock, scc_cnt, sccno[N];stack<int >S;void dfs(int u){ pre[u] = lowlink[u] = ++dfs_clock; S.push(u); int siz = G[u].size(); for(int i=0; i<siz; i++) { int v = G[u][i]; if(!pre[v]) { dfs(v); lowlink[u] = min(lowlink[u], lowlink[v]); } else if(!sccno[v]) { lowlink[u] = min(lowlink[u], pre[v]); } } if(lowlink[u] == pre[u]) { scc_cnt++; for(;;) { int x = S.top(); S.pop(); sccno[x] = scc_cnt; num[scc_cnt]++; if(x==u) break; } }}void find_scc(){ dfs_clock = 0; scc_cnt = 0; memset(sccno, 0, sizeof(sccno)); memset(pre, 0, sizeof(pre)); for(int i=1; i<=n; i++) { if(!pre[i]) dfs(i); }}void solve(){ scanf("%d%d", &n ,&m); memset(num, 0, sizeof(num)); memset(in, 0, sizeof(in)); memset(out, 0, sizeof(out)); for(int i=1; i<=n ;i++) G[i].clear(); int u, v; for(int i=0; i<m; i++) { scanf("%d%d", &u, &v); G[u].push_back(v); } find_scc(); printf("Case %d: ", cas++); if(scc_cnt==1) { printf("-1\n"); return ; } ll ans = 0, Min = INF; for(int i=1; i<=n; i++) { int siz = G[i].size(); for(int j=0; j<siz; j++) { if(sccno[i]!=sccno[G[i][j]]) { in[sccno[G[i][j]]]++; out[sccno[i]]++; } } } for(int i=1; i<=scc_cnt; i++) { if((in[i]==0 || out[i]==0) && Min>num[i]) Min = num[i];// printf("num[%d] = %d\n", i, num[i]);// printf("out = %d, in = %d\n", out[i], in[i]); } ans = (Min-1)*Min- m + (n-Min)*(n-Min-1)+Min*(n-Min); cout<<ans<<endl;}int main(){// freopen("in", "r", stdin); cin>>_; while(_--) solve(); return 0;}
![KX9HZK]4LPXQ]63U2%VM$NX](/d/file/p/2024/07/16/b48fd36436be66177e50ff8120ab2d44.jpg "KX9HZK]4LPXQ]63U2%VM$NX")
”，弱菜被骂傻，也很正常啦
。
