题面

题意

• 有一个 $n\times n$ 的矩阵，$m$ 个点可以填数，给定两个数组 $r$ 和 $c$，$r[i]$ 表示第 $i$ 行的最大元素，$c[i]$ 表示第 $i$ 列的最大元素，需要在这 $m$ 个点中填值，在满足 $r$ 和 $c$ 数组的条件下求矩阵最小和。
• $1\le n\le 2\times 10^3,1\le m\le 8\times 10^5,1\le k\le 10^6,1\le b_i,c_i\le k$，$b_i,c_i$ 最多有 500 个值

思路

1. 考虑到每一种 $b_i,c_i$ 独立，只有 $b_i=c_i$ 才能减少答案，此时行列共用一个最大值。将行与列抽象成二分图的两边的点。$b_i=c_i$ 时两个点连一条边，因为每一行与每一列连一条边后不能再连边减少答案，这就是二分图的性质，所以现在等价于求二分图的最大匹配。考虑所有 $b_i=c_i$ 的情况，分别建图跑最大流即可。

代码

const int N = 2e3 + 5, M = 1e6;ll ans;
int row[N], col[N];
int n, m, k, S, T, f[M];
int h[N], e[M], ne[M], idx;
int d[N], cur[N];
bool vis[N][N];
vi tr[M], tc[M];void add(int u, int v, int c) {e[idx] = v, f[idx] = c, ne[idx] = h[u], h[u] = idx++;e[idx] = u, f[idx] = 0, ne[idx] = h[v], h[v] = idx++;
}void init() {mst(h, -1); idx = 0;}void inp() {init();cin >> n >> m >> k;S = N - 2, T = N - 1;rep(i, 1, n) row[i] = rd, tr[row[i]].pb(i);rep(i, 1, n) col[i] = rd, tc[col[i]].pb(i);rep(i, 1, m) {int u = rd, v = rd;vis[u][v] = true;}
}bool bfs() {queue<int> q;mst(d, -1);q.push(S), d[S] = 0, cur[S] = h[S];while(!q.empty()) {int u = q.front(); q.pop();for(int i = h[u]; ~i; i = ne[i]) {int v = e[i];if(d[v] == -1 && f[i]) {d[v] = d[u] + 1;cur[v] = h[v];if(v == T) return true;q.push(v);}}}return false;
}int find(int u, int limit) {if(u == T) return limit;int flow = 0;for(int i = cur[u]; ~i && flow < limit; i = ne[i]) {int v = e[i];cur[u] = i;if(d[v] == d[u] + 1 && f[i]) {int t = find(v, min(f[i], limit - flow));if(!t) d[v] = -1;f[i] -= t, f[i ^ 1] += t, flow += t;}}return flow;
}int dinic() {int ret = 0, flow = 0;while(bfs()) {while(1) {flow = find(S, inf); ret += flow;if(!flow) break;}}return ret;
}int main() {inp();per(i, k, 1) {init();int dx = sz(tr[i]);for(int ele : tr[i]) add(S, ele, 1);for(int ele : tc[i]) add(ele + dx, T, 1);for(int ele1 : tr[i]) for(int ele2 : tc[i])if(vis[ele1][ele2]) add(ele1, ele2 + dx, 1);ans += (ll)(sz(tr[i]) + sz(tc[i]) - dinic()) * i;}cout << ans << endl;return 0;
}