相关链接
题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/07/NOI2017-matthew99.pdf
解题报告
我们按照极角序来贪心匹配
不难发现这样一定有解
另外Dinic是不能求这种要求字典序最小的解的
似乎只能用最裸的匈牙利
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 1009; const int M = 1000009; const int INF = 1e9; const double PI = acos(-1); int n, R, D, S, T; int in[N], ot[N], cnt_in, cnt_ot; int head[N], nxt[M], to[M], mth[N], vis[N]; pair<double, int> arr[N]; struct Point{ int x, y, ty; inline int dis(const Point &P) { return (x - P.x) * (x - P.x) + (y - P.y) * (y - P.y); } }p[N]; inline void AddEdge(int u, int v) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; } inline int read() { char c = getchar(); int ret = 0, f = 1; while (c < '0' || c > '9') { f = c == '-'? -1: 1; c = getchar(); } while ('0' <= c && c <= '9') { ret = ret * 10 + c - '0'; c = getchar(); } return ret * f; } inline bool DFS(int w) { vis[w] = 1; for (int i = head[w]; i; i = nxt[i]) { if (!mth[to[i]] || (!vis[mth[to[i]]] && DFS(mth[to[i]]))) { mth[to[i]] = w; mth[w] = to[i]; return 1; } } return 0; } inline int solve() { int ret = 0; for (int ii = 1, i; i = in[ii], ii <= cnt_in; ii++) { if (!mth[i]) { memset(vis, 0, sizeof(vis)); ret += DFS(i); } } return ret; } inline void print(int w) { for (int i = head[w]; i; i = nxt[i]) { if (to[i] == mth[w]) { vis[w] = vis[to[i]] = 1; printf("%d %d\n", w, mth[w]); return; } else if (!vis[to[i]]){ print(mth[to[i]]); } } } int main() { n = read(); R = read(); R *= R; D = read(); D *= D; S = 0; T = N - 1; for (int i = 1; i <= n; i++) { p[i].x = read(); p[i].y = read(); if (p[i].ty = p[i].dis(p[1]) > R) { in[++cnt_in] = i; } else { ot[++cnt_ot] = i; } } for (int ii = 1; ii <= cnt_in; ii++) { int i = in[ii], cnt_arr = 0; double mx = -PI, mn = PI; for (int jj = 1; jj <= cnt_ot; jj++) { int j = ot[jj]; if (p[i].dis(p[j]) <= D) { double agl = atan2(p[j].y - p[i].y, p[j].x - p[i].x); mx = max(mx, agl); mn = min(mn, agl); arr[++cnt_arr] = make_pair(agl, j); } } if (mx - mn >= PI) { for (int j = 1; j <= cnt_arr; j++) { arr[j].first += arr[j].first < 0? PI * 2: 0; } } sort(arr + 1, arr + 1 + cnt_arr); for (int j = 1; j <= cnt_arr; j++) { AddEdge(i, arr[j].second); } } printf("%d\n", solve() << 1); memset(vis, 0, sizeof(vis)); for (int ii = 1, i; i = in[ii], ii <= cnt_in; ii++) { if (mth[i] && !vis[i]) { print(i); } } return 0; }