题目大意：
添加尽可能少的边，最后使图形成二分图
一开始将图区分成一个个联通分量，根据二分图染色，计算出每个联通分量的黑色点和白色点的个数
希望添加的边最少，那么合并的时候，希望黑白块尽可能平均，这无疑背包dp做，但超时了。。。T T
跟着题解说的bitset，学了一下，果然总共10000个点不到，那么只要用bitset上的某一位代表取到的值即可- -，好神奇。。这里用的是或运算
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <map> 5 #include <vector> 6 #include <queue> 7 #include <climits> 8 #include <bitset> 9 #include <algorithm> 10 using namespace std; 11 #define ls o<<1 12 #define rs o<<1|1 13 #define define_m int m=(l+r)>>1 14 #define N 10010 15 #define ll long long 16 vector <int> vec[N]; 17 bitset<10001> bt; 18 int n , m , u , v , id; 19 int w[N] , b[N] ,col[N]; 20 21 void dfs(int u , int id) 22 { 23 if(col[u]) w[id]++; 24 else b[id]++; 25 int l = vec[u].size(); 26 for(int i=0 ; i<l ; i++){ 27 int v = vec[u][i]; 28 if(col[v]>=0) continue; 29 col[v] = col[u]^1; 30 dfs(v , id); 31 } 32 } 33 34 void solve() 35 { 36 memset(b, 0,sizeof(b)); 37 memset(w , 0 , sizeof(w)); 38 memset(col , -1 , sizeof(col)); 39 id = 0; 40 for(int i=1 ; i<=n ; i++){ 41 if(col[i]<0){ 42 ++id; 43 col[i] = 0; 44 dfs(i , id); 45 } 46 } 47 } 48 49 int cal() 50 { 51 bt[0] = 1; 52 for(int i=1 ; i<=id ; i++){ 53 bt = bt|(bt<<b[i])|(bt<<w[i]); 54 } 55 int ans = n , ave = n/2; 56 for(int i=0 ; i<=n ; i++){ 57 if(bt[i]){ 58 if(abs(ans-ave)>abs(i-ave)) ans = i; 59 } 60 } 61 return ans*(n-ans)-m; 62 } 63 64 int main() 65 { 66 //freopen("in.txt" , "r" , stdin); 67 int T; 68 scanf("%d" , &T); 69 while(T--) 70 { 71 scanf("%d%d" , &n , &m); 72 for(int i=1 ; i<=n ; i++)vec[i].clear(); 73 for(int i=0 ; i<m ; i++){ 74 scanf("%d%d" , &u , &v); 75 vec[u].push_back(v); 76 vec[v].push_back(u); 77 } 78 solve(); 79 printf("%d " , cal()); 80 } 81 return 0; 82 }