2
4 2
1 2
2 3
4 4
1 2
1 4
2 3
3 4

 

2
0

 题意，给个二分图，要求添加最多的边形成一个完全二分图。

我们知道对于一个完全二分图，其边数为 x * y;xy分别为二分图两个集合的点数。那么如果给出的一个二分图，我们知道其可能并不是一个连通图，那么，用深搜，找出若干个小的二分图，只需要，合并若干个二分图，最终使得，整个二分图的两个集合的点数越接近，那么边数最多，加的边数也就最多。用dp的方法,dp[i]表示前i个二分图所能形成的最大点数（不超过n/2），状态转移就是dp[i] = dp[i-1] + x（x为一个二分图的点数。）这里用bitset优化，虽然是O(n*n)的复杂度也能过。还有方法，是用贪心的方法。把所有的二分图随机分入到x集和y集，得到x,y.然后，把x,y直接往n/2来凑，只要o(1)的复杂度，个人觉得这种方法，没有道理吧。但是由于，反例，还真的很难找出来，如果边太少，那么这种贪心方法，x,y必然可以达到接近n/2,如果边很多，又会形成一个大的整体，所以也没多大问题吧。故这样，也能过这题。

#define N 10005
#define M 100005
#define maxn 205
#define MOD 1000000007
int n,m,a,b,c,vis[N],ans[N][2],T;
vector<int> p[N];
bitset<N> sum;
void DFS(int f,int root){
    FI(p[f].size()){
        int v = p[f][i];
        if(vis[v] == -1){
            vis[v] = 1 - vis[f];
            ans[root][vis[v]]++;
            DFS(v,root);
        }
    }
}
int main()
{
    while(S(T)!=EOF)
    {
        while(T--){
            S2(n,m);
            FI(n) p[i+1].clear();
            FI(m){
                scan_d(a);scan_d(b);
                p[a].push_back(b);
                p[b].push_back(a);
            }
            memset(vis,-1,sizeof(vis));
            fill(ans,0);
            for(int i = 0;i<= n;i++) sum[i] = 0;
            sum[0] = 1;
            for(int i= 1;i<=n;i++){
                if(vis[i] == -1){
                    vis[i] = 0;ans[i][vis[i]]++;
                    DFS(i,i);//cout<<ans[i][0]<<" i "<<ans[i][1]<<endl;
                    sum|= ( sum << ans[i][0]) | ( sum << ans[i][1]);
                }
            }
            int maxx = 0;
            for(int i = n;i>=0;i--)
                if(sum[i])
                    maxx = max(maxx,i * (n - i) - m);
            printf("%d\n",maxx);
        }
    }
    return 0;
}