题面
平面上有(n)个点((x_i, y_i))，每个点两种权值(a_i, b_i)，(m)条边连接这(n)个点，每条边权值(c_i)
边把平面分成很多块，每个块两种权值(A_i, B_i)，(A_i)是它边界上所有点(a_i)之和，(B_i)是它边界上所有点(b_i)之和（最外面的无穷域边界认为是凸包上的点）
每个块可以选择(A_i)或(B_i)一种权值加入收益，如果两个相邻的块权值种类不同，收益扣除它们之间的边的权值
求最大收益
(n le 4e4, m le 2e5, |x_i|, |y_i| le 2e4, 0 le c_i le 1e6, 0 le a_i, b_i le 1e3)
保证分割出的块数(C le 4e4)
解析
显然的平面图转对偶图，然后就可以跑最小割了
然后建图建错了，数据仁慈给了(52pts)
但是复杂度(O(n + m log m + maxflow(C, m + C)))居然真的能跑过……
果然网络流复杂度是(O(?))的……
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#define MAXN 40005
#define MAXM 200005
typedef long long LL;
const double PI = acos(-1);
const LL INF = 0x3f3f3f3f3f3f3f3f;
struct Graph {
struct Edge {
int v, next; LL cap;
Edge(int _v = 0, int _n = 0, LL _c = 0):v(_v), next(_n), cap(_c) {}
} edge[(MAXN + MAXM) << 2];
int head[MAXN << 1], dep[MAXN << 1], cur[MAXN << 1], cnt, S, T;
void init() { memset(head, -1, sizeof head); cnt = 0; }
void add_edge(int u, int v, LL c) { edge[cnt] = Edge(v, head[u], c); head[u] = cnt++; }
void insert(int u, int v, LL c) { add_edge(u, v, c); add_edge(v, u, 0); }
bool bfs();
LL dfs(int, LL);
LL dinic();
};
struct Point {
int x, y, a, b;
};
struct Vector {
int v, cost; double ang;
Vector(int = 0, int = 0, int = 0);
bool operator <(const Vector &v) const { return ang < v.ang; }
};
char gc();
int read();
void build();
Vector E[MAXM << 1];
Graph G;
std::vector<int> g[MAXN];
Point pt[MAXN];
int N, M, NUM, tot;
int bel[MAXM << 1], next[MAXM << 1];
LL val1[MAXN], val2[MAXN];
bool vis[MAXM << 1];
bool cmp(const int &a, const int &b) { return E[a].ang < E[b].ang; }
int main() {
freopen("everfeel.in", "r", stdin);
freopen("everfeel.out", "w", stdout);
NUM = read(), N = read(), M = read();
for (int i = 1; i <= N; ++i)
pt[i].x = read(), pt[i].y = read(), pt[i].a = read(), pt[i].b = read();
for (int i = 0; i < M; ++i) {
int u = read(), v = read(), c = read();
E[i << 1] = Vector(u, v, c), g[u].push_back(i << 1);
E[i << 1 | 1] = Vector(v, u, c), g[v].push_back(i << 1 | 1);
}
build();
//memory test
//while(1);
if ((NUM > 2 && NUM < 7) || (NUM > 10 && NUM < 13) || (NUM > 16 && NUM < 20)) {
LL ans = 0;
for (int i = 1; i <= tot; ++i) ans += std::max(val1[i], val2[i]);
printf("%lld
", ans);
} else {
LL ans = 0;
for (int i = 1; i <= tot; ++i) ans += val1[i] + val2[i];
printf("%lld
", ans - G.dinic());
}
return 0;
}
inline char gc() {
static char buf[1000000], *p1, *p2;
if (p1 == p2) p1 = (p2 = buf) + fread(buf, 1, 1000000, stdin);
return p1 == p2 ? EOF : *p2++;
}
inline int read() {
int res = 0, op; char ch = gc();
while (ch != '-' && (ch < '0' || ch > '9')) ch = gc();
op = (ch == '-' ? ch = gc(), -1 : 1);
while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + ch - '0', ch = gc();
return res * op;
}
Vector::Vector(int _u, int _v, int _c):v(_v), cost(_c) { ang = atan2(pt[_v].y - pt[_u].y, pt[_v].x - pt[_u].x); }
void build() {
for (int i = 1; i <= N; ++i) std::sort(g[i].begin(), g[i].end(), cmp);
for (int i = 0; i < (M << 1); ++i) {
int v = E[i].v;
std::vector<int>::iterator it = ++std::lower_bound(g[v].begin(), g[v].end(), i ^ 1, cmp);
if (it == g[v].end()) it = g[v].begin();
next[i] = *it;
}
for (int i = 0; i < (M << 1); ++i) if (!vis[i]) {
++tot;
for (int j = i; !vis[j]; j = next[j]) vis[j] = 1, bel[j] = tot;
}
G.init();
for (int i = 0; i < (M << 1); ++i) {
int u = bel[i], v = bel[i ^ 1], c = E[i].cost;
val1[u] += (LL)pt[E[i].v].a, val2[u] += (LL)pt[E[i].v].b;
if (u > v) continue;
G.add_edge(u, v, c), G.add_edge(v, u, c);
}
for (int i = 1; i <= tot; ++i) {
G.insert(0, i, val1[i]);
G.insert(i, tot + 1, val2[i]);
}
G.S = 0, G.T = tot + 1;
}
bool Graph::bfs() {
static int q[MAXN], hd, tl;
hd = tl = 0;
memset(dep, 0, sizeof dep);
q[tl++] = S, dep[S] = 1;
while (hd < tl) {
int p = q[hd++];
if (p == T) return 1;
for (int i = head[p]; ~i; i = edge[i].next)
if (edge[i].cap && !dep[edge[i].v]) {
dep[edge[i].v] = dep[p] + 1;
q[tl++] = edge[i].v;
}
}
return 0;
}
LL Graph::dfs(int u, LL maxflow) {
if (u == T) return maxflow;
LL res = 0;
for (int &i = cur[u]; ~i; i = edge[i].next)
if (edge[i].cap && dep[edge[i].v] == dep[u] + 1) {
LL d = dfs(edge[i].v, std::min(edge[i].cap, maxflow));
if (d) {
res += d, maxflow -= d;
edge[i].cap -= d, edge[i ^ 1].cap += d;
if (!maxflow) break;
}
}
if (!res) dep[u] = -1;
return res;
}
LL Graph::dinic() {
LL res = 0;
while (bfs()) {
memcpy(cur, head, sizeof head);
res += dfs(S, INF);
}
return res;
}
//Rhein_E O(?)