hdu4635（最多加多少边，使得有向图不是强连通图）

连边的最后肯定是两个集合x,y
x集合的每个元素，到y集合中的每个元素都是单向的边
x集合，和y集合都是完全图
设a为x集合的点的个数， b为y集合的
那么答案就是 a * b + a*(a-1) + b*(b-1) - m
n*n-a*b-n-m , 所以a*b尽量小，即a和b的差值尽量大

缩点之后的点入度为0，或者出度为0才能成为x集合，y集合

  1 #pragma warning(disable:4996)
  2 #pragma comment(linker, "/STACK:1024000000,1024000000")
  3 #include <iostream>
  4 #include <stdio.h>
  5 #include <string.h>
  6 #include <vector>
  7 #include <stack>
  8 #include <queue>
  9 #include <math.h>
 10 #include <algorithm>
 11 #include <map>
 12 #include <set>
 13 #include <functional>
 14 using namespace std;
 15 typedef __int64 LL;
 16 const int N = 100000 + 10;
 17 int dfn[N], low[N], sccno[N], cnt, dfs_clock, sum[N], in[N], out[N];
 18 vector<int> g[N];
 19 stack<int> st;
 20 /*
 21 
 22 
 23 */
 24 void init(int n)
 25 {
 26     cnt = dfs_clock = 0;
 27     for (int i = 0;i <= n;++i)
 28     {
 29         
 30         in[i] = out[i] = dfn[i] = low[i] = sccno[i] = sum[i] = 0;
 31         g[i].clear();
 32     }
 33 }
 34 void tarjan(int u, int fa)
 35 {
 36     dfn[u] = low[u] = ++dfs_clock;
 37     st.push(u);
 38     for (int i = 0; i<g[u].size(); ++i)
 39     {
 40         int v = g[u][i];
 41         if (dfn[v] == 0)
 42         {
 43             tarjan(v, u);
 44             low[u] = min(low[u], low[v]);
 45         }
 46         else if (sccno[v] == 0)//因为有向图存在横插边，不能用横插边来更新low[u]
 47         {
 48             low[u] = min(low[u], low[v]);
 49         }
 50     }
 51     //同样，因为强连通分量可以分布在根结点的两个分支上，所以在递归返回的时候调用
 52     if (low[u] == dfn[u])
 53     {
 54         cnt++;
 55         for (;;)
 56         {
 57             int x = st.top();
 58             st.pop();
 59             sccno[x] = cnt;
 60             sum[cnt]++;
 61             if (x == u)
 62                 break;
 63         }
 64     }
 65 }
 66 
 67 int main()
 68 {
 69     int t, n, m;
 70     int u, v;
 71     scanf("%d", &t);
 72     for (int k = 1;k <= t;++k)
 73     {
 74         scanf("%d%d", &n, &m);
 75         init(n);
 76         for (int i = 1;i <= m;++i)
 77         {
 78             scanf("%d%d", &u, &v);
 79             g[u].push_back(v);
 80             
 81         }
 82         for (int i = 1;i <= n;++i)
 83             if (dfn[i] == 0)
 84                 tarjan(i, -1);
 85         for (int u = 1;u <= n;++u)
 86         {
 87             for (int i = 0;i < g[u].size(); ++i)
 88             {
 89                 int v = g[u][i];
 90                 if (sccno[u] != sccno[v])
 91                 {
 92                     in[sccno[v]]++;
 93                     out[sccno[u]]++;
 94                 }
 95             }
 96         }
 97         if (cnt == 1)
 98         {
 99             printf("Case %d: -1
", k);
100             continue;
101         }
102         LL ans = 0;
103         for (int i = 1;i <= cnt;++i)
104         {
105             if (!in[i] || !out[i])//出度为0或者入度为0的连通分量才能成为一个集合，剩余的成为另一个集合
106             {
107                 LL a = sum[i];
108                 LL b = n - a;
109                 ans = max(ans, n*n - a*b - n - m);
110             }
111         }
112         printf("Case %d: %I64d
", k, ans);
113     }
114     return 0;
115 }