题目大意：给出一张DAG(n个点，m条边)，求出能加的最大边数，使得该图无重边，无自环，非强连通。
题解：这题题面很好理解，也没有什么很难的点，主要是如何求出最大边数需要动点脑筋。首先要明确一点强连通图不一定是完全图，完全图一定是强连通图。因为完全图定义是任意两点均有连边，而强连通仅为任意两点可互相到达。于是乎这题我们可以这样构思，最后我们要的是这样一张图，有若干条有向边，连接着两张完全子图，那么问题就来了，如何构造这两张完全子图？不妨设这两张完全子图为G1，G2，其顶点数分别为V1，V2（V1+V2=n），可知边数为V1*V2+V1*(V1-1)+V2*(V2-1)，V1*V2即为上文所言若干条边，剩余两项即为G1，G2完全图的边数。化简可得n*(n-1)-(n-V1)*V1，注意这不是答案，因为题目给了m条边，所以还要扣除m，那么问题就来了，如何使得答案——n*(n-1)-m-(n-V1)*V1最大？其实很容易想到，因为n，m是常数，所以V1就是关键，而V1+V2=n那么上式中n-V1即为V2，那么如何使V1*V2最小？由基本不等式( a^2 + b^2 >= 2ab)，可得，我们应该使V1、V2差值尽量大，那么就可以统计一下各个强连通分量的大小，使最小的为V1，然后带入n*(n-1)-m-(n-V1)*V1，就解决完了本题。其实就是有多个强连通分量，选最小的并且出度或者入度为0的当V1，剩下的去拼成一张完全图，就得到了G1、G2，然后就是上述说明了。
对于入度或者出度为0的解释：因为我们的构想是要两张完全子图G1、G2，然后G1、G2之间的若干条边，均用G1(G2)指向G2(G1)，所以如果桥上有点，应该归入与之相连的较大的完全子图中。
#include#include #include #include #include #define mem(a,b) memset((a),(b),sizeof(a))using namespace std;const int N = 1e5 + 16;const int INF = 0x3f3f3f3f;typedef long long ll;struct Edge{ int u, v, nxt;};Edge edge[N<<1];bool vis[N];int sta[N], dfn[N], low[N];int ecnt, head[N];int in[N], out[N], cnt[N];int col[N], sum, dep, top;void init(){ mem(vis,0); mem(head,-1); mem(in,0); mem(out,0); mem(sta,0); mem(dfn,0); mem(low,0); mem(cnt,0); mem(col,0); sum = ecnt = dep = top = 0;}void _add( int _u, int _v ){ edge[ecnt].u = _u; edge[ecnt].v = _v; edge[ecnt].nxt = head[_u]; head[_u] = ecnt ++;}void tarjan( int u ){ sta[++top] = u; low[u] = dfn[u] = ++dep; vis[u] = 1; for ( int i = head[u]; i+1; i = edge[i].nxt ) { int v = edge[i].v; if ( !dfn[v] ) { tarjan(v); low[u] = min( low[u], low[v] ); } else if ( vis[v] ) { low[u] = min( low[u], low[v] ); } } if ( low[u] == dfn[u] ) { vis[u] = 0; col[u] = ++sum; while ( sta[top] != u ) { vis[sta[top]] = 0; col[sta[top--]] = sum; } top --; }}int main(){ int T; scanf("%d", &T); for ( int cas = 1; cas <= T; cas ++ ) { init(); int n, m; scanf("%d%d", &n, &m); for ( int i = 0; i < m; i ++ ) { int u, v; scanf("%d%d", &u, &v); _add(u,v); } for ( int i = 1; i <= n; i ++ ) if ( !dfn[i] ) tarjan(i); for ( int i = 1; i <= n; i ++ ) { cnt[col[i]] ++; for ( int j = head[i]; j+1; j = edge[j].nxt ) { int v = edge[j].v; if ( col[v] != col[i] ) { in[col[v]] ++; out[col[i]] ++; } } } if ( sum == 1 ) { printf("Case %d: %d\n", cas, -1); } else { int mn = INF; for ( int i = 1; i <= sum; i ++ ) if ( in[i] == 0 || out[i] == 0 ) mn = min( mn, cnt[i] ); ll ans = n*(n-1)*1ll - m*1ll - mn*(n-mn)*1ll; printf("Case %d: %lld\n", cas, ans); } } return 0;}