思路与算法

将每张矩形与其包含的数字点连边，得到二分图。先用增广路找一个完美匹配；找不到则None。若找到，对该匹配中的每一条边分别禁止，再重新求完美匹配。任何一次仍可完美匹配都说明有第二种对应，输出None；全部失败则原匹配唯一，按矩形字母输出。

正确性说明

合法双射与完美匹配一一对应。若有第二个完美匹配，它必与第一个匹配至少有一条边不同，所以禁止第一个匹配中这条边后，第二个仍然存在。反之，禁止一条原匹配边后得到的完美匹配显然不同。因此逐一禁边测试当且仅当判出多解；剩余唯一匹配正是所求对应。

复杂度

建包含关系O(n²)，一次增广路匹配O(n³)，最多再做n次，总时间O(n⁴)；空间O(n²)，含邻接表与匹配数组。n≤26可直接执行。

易错点

边界按闭矩形包含。不能找到一个完美匹配就立即输出，还要排除第二个解。None既包括完全无解，也包括不唯一。删掉某条匹配边后必须重新初始化整个匹配状态。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> g;
vector<int> mt, seen;
int bu, bv;
bool dfs(int u) {
    for (int v : g[u])
        if (!(u == bu && v == bv) && !seen[v]) {
            seen[v] = 1;
            if (mt[v] < 0 || dfs(mt[v])) {
                mt[v] = u;
                return true;
            }
        }
    return false;
}
bool match(int u = -1, int v = -1) {
    bu = u;
    bv = v;
    mt.assign(n, -1);
    for (int i = 0; i < n; ++i) {
        seen.assign(n, 0);
        if (!dfs(i))
            return false;
    }
    return true;
}
int main() {
    cin >> n;
    vector<array<int, 4>> r(n);
    for (auto &a : r)
        for (int &x : a)
            cin >> x;
    g.resize(n);
    for (int j = 0; j < n; ++j) {
        int x, y;
        cin >> x >> y;
        for (int i = 0; i < n; ++i)
            if (r[i][0] <= x && x <= r[i][1] && r[i][2] <= y && y <= r[i][3])
                g[i].push_back(j);
    }
    if (!match()) {
        cout << "None\n";
        return 0;
    }
    vector<int> ans(n);
    for (int j = 0; j < n; ++j)
        ans[mt[j]] = j;
    for (int i = 0; i < n; ++i)
        if (match(i, ans[i])) {
            cout << "None\n";
            return 0;
        }
    for (int i = 0; i < n; ++i)
        cout << char('A' + i) << ' ' << ans[i] + 1 << "\n";
}