比较符合 CCF 造数据水平的题。

思路

首先可以用两个 vector<pair<int,int>> v[N] 分别将每一行、每一列的元素的权值与编号存储下来。

那么可以对所有的 \(v_i\) 按照权值从小到大排序。那么发现对于所有的满足 v[i][p].fst < v[i][q].fst 的 \((p,q)\) 都可以建一条从 \(p\) 指向 \(q\) 的有向边。按照这种方式建图，最坏情况下会有 \(\Theta(n^2)\) 级别的边。

考虑一种比较显然的贪心策略，对于一个 \(p\) 显然只需要与 \(p\) 之后第一个满足 v[i][p].fst < v[i][q].fst 连边。因为如果不这么连，将 \(p\) 连向一个拥有更大权值的点 \(k\)，显然你可以通过 \(p \to q \to k\) 的方式获得更大的答案。

于是你写完过后交上去，发现会WA 1。这其中的原因就是对于权值相同的几个点，你直接取第一个是不优的。

不难发现，我们希望将所有满足条件的相同权值的点都要连边，同时保证边数尽量小。不妨考虑将这些点直接看作一个点，实现的话可以直接将这些权值相同的点连向一个超级原点，在后面连边的时候用超级原点与现在的点连边即可。

现在问题就很简单了，直接建反图，跑一边拓扑h

Code