emmmmmmm不错的的最小割吧
唯一一个不是很好的点就是实在是太容易想到是最小割了，但是没想到具体的建图方法。
题意：
有n个点，m条边，要你分成两个集合，使得两个集合的导出子图各自权值和的和最大。
两个导出子图中，可选择其中一个，若导出子图中存在有两个点 (i,j) 相连，则该导出子图权值增加 $| i-j |$ 。同时另一个导出子图则相反，只有存在两个点没有边相连，才会增加权值。
思路：
题目的主要目的就是将点集分成两部分，这很容易想到二分图染色，但这是不现实的，因为这是一个最值问题，不存在必然关系。
而跟二分图相关的只有网络流了，将图分为两半是割的概念，当然只存在最小割，正面去想的话，就是总权值和-最小割。
然后……思路就断了，找不到有效的建图方法。
可以先这么想，我们假定与源点相连的点集为相连增加权值的集合，并称之为，与汇点相连的点集则相反，称之为汇点集。
那么我们先将每个点都与源点相连，其容量为将该点加入源点集所能增加的权值。
再将这个点与汇点相连，其容量为将该点加入汇点集所能增加的权值。
此时直接跑最小割是不对的，因为这些点并不是独立的。
其实只要再将任意两个点都连边就可以了。
啊，顺便发现一个，换一种无向图建边，速度快了一倍，因为边几乎少了一半
AC Code
#include <cstdio>
#include <cstring>
#include <queue>
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e3 + 5;
const int maxm = 5e6 + 5;
const int inf = 0x3f3f3f3f;
int src, des, idx;
int cur[maxn], level[maxn], head[maxn];
struct node {
int to, next;
int cap;
node() {}
node(int _to, int _next, int _cap) { to = _to, next = _next, cap = _cap; }
} edges[maxm << 1];
queue<int> que;
void addEdge(int u, int v, int c, int rc = 0)
{
edges[idx] = node(v, head[u], c);
head[u] = idx++;
edges[idx] = node(u, head[v], rc);//无向边建边小技巧
head[v] = idx++;
}
bool bfs()
{
memset(level, -1, sizeof level);
que.push(src);
level[src] = 0;
int u;
while (!que.empty()) {
u = que.front();
que.pop();
for (int id = head[u]; ~id; id = edges[id].next) {
int v = edges[id].to;
if (edges[id].cap > 0 && level[v] == -1) {
level[v] = level[u] + 1;
que.push(v);
}
}
}
return level[des] != -1;
}
int dfs(int u, int low)
{
int cflow;
if (u == des)
return low;
for (int& id = cur[u]; ~id; id = edges[id].next) {
int v = edges[id].to;
if (edges[id].cap > 0 && level[v] == level[u] + 1
&& (cflow = dfs(v, min(low, edges[id].cap)))) {
edges[id].cap -= cflow;
edges[id ^ 1].cap += cflow;
return cflow;
}
}
return 0;
}
int dinic(int n)
{
int ans = 0, cflow;
while (bfs()) {
for (int i = 0; i <= n + 1; i++)
cur[i] = head[i];
while ((cflow = dfs(src, inf)))
ans += cflow;
}
return ans;
}
void init(int s, int d)
{
memset(head, -1, sizeof head);
idx = 0;
src = s, des = d;
}
bool g[maxn][maxn];
int s[maxn], t[maxn];
inline void scan_d(int& num)
{
char in;
in = getchar();
while (in != '-' && (in < '0' || in > '9'))
in = getchar();
num = in - '0';
while (in = getchar(), in >= '0' && in <= '9') {
num *= 10, num += in - '0';
}
}
int main()
{
int n, m, u, v, tmp;
scan_d(n), scan_d(m);
init(0, n + 1);
while (m--) {
scan_d(u), scan_d(v);
g[u][v] = g[v][u] = true;
}
range(i, 1, n) range(j, i + 1, n)
{
tmp = j - i;
if (g[i][j])
s[i] += tmp, s[j] += tmp;
else
t[i] += tmp, t[j] += tmp;
addEdge(i, j, tmp, tmp);
}
int ans = 0;
range(i, 1, n) addEdge(src, i, s[i]), addEdge(i, des, t[i]);
range(i, 1, n) ans += (1 + n - i) * (n - i) / 2;
printf("%d\n", ans - dinic(n) / 2); //因为与源点汇点相连的点增加了一倍权值
return 0;
}