题目描述：
给定一张图。求将这张图分成两个完全子图后，最少会有多少条边的端点属于同一个完全子图。
数据范围：
\(1\leq n\leq 700\)
思路；
发现这个 \(n\) 的范围非常小，所以他支持 \(n^2\) 的做法。
然后我们思考怎么转换一下这个问题。显然如果是完全子图的话，就不是很方便处理。在审题的时候，你看到分成两部分，难道不会联想到一些东西吗？
比如二分图。然后我们总觉得这个完全子图 比较碍事，很讨厌，不好处理，所以考虑建出补图。
根据补图的定义，完全子图 就变为 两两不相连 的子图。然后就可以将原问题转换为二分图来处理了。
然后我们对于一个二分图进行染色，令黑点（0）的个数未 \(a\)，白点（1）的个数未 \(b\)，则边数（即答案）为 \(\frac{a\times (a-1)}{2}+\frac{b\times (b-1)}{2}\to \frac{a^2-a+b^2-b}{2}\)
然后我们对上述的式子进行一些转换：\(\frac{a^2+2ab+b^2-(a+b)-2ab}{2}\to \frac{(a+b)(a+b-1)-2ab}{2}\)，即 \(\frac{n\times (n+1)-2ab}{2}\)
所以如果想要将答案变得尽可能小，则 \(2ab\) 需要尽可能大，即两个数的差尽可能小。
然后思考怎么解决这个问题。这时候就需要将最优化问题转换为可行性问题了。使用 \(Dp\) 可以快速求出最小差值，然后通过和差问题来直接计算这个答案。
但是还有一种更为简单粗暴的方式：直接使用 \(bitset\) 去优化背包，复杂度 \(O(\frac{n^2}{\omega})\)
这里就只提供后面一种方式的代码，毕竟简单直接。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int maxn=705;
int n,m;
int calc(int x){
return x*(x-1)/2+(n-x)*(n-x-1)/2;
}
int g[maxn][maxn];
vector<int>G[maxn];
int col[maxn],cnt[2],vis[maxn];
void dfs(int u,int c){
cnt[c]++;
col[u]=c;
vis[u]=1;
for(int v:G[u]){
if(!vis[v]){
dfs(v,c^1);
}
else if(col[v]==c){
puts("-1");
exit(0);
}
}
}
bitset<700*700+5>dp;
signed main(){
cin>>n>>m;
dp[0]=1;
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
g[u][v]=g[v][u]=1;
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(!g[i][j]){
G[i].pb(j);
G[j].pb(i);
}
}
}
memset(col,-1,sizeof(col));
for(int i=1;i<=n;i++){
if(!vis[i]){
cnt[0]=cnt[1]=0;
dfs(i,0);
dp=(dp<<cnt[0])|(dp<<cnt[1]);
}
}
int ans=0x3f3f3f3f;
for(int i=1;i<=n;i++){
if(dp[i]){
ans=min(ans,calc(i));
}
}
cout<<ans<<endl;
return 0;
}