题意：给定一个矩阵，每列有两个白点，其它都是黑点，如今要求每列选一个白点，使得每一行至少包括一个白点被选中
思路：利用白点所在的位置用行指向列建图，用行去匹配列，最大匹配数假设不等于行数的话，就无解。
代码：
#include#include #include #include #include using namespace std;const int MAXN = 1005;vector g[MAXN];int linker[MAXN];bool used[MAXN];int r, c;bool dfs(int u) { for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (!used[v]) { used[v] = true; if (linker[v] == -1 || dfs(linker[v])) { linker[v] = u; return true; } } } return false;}int save[MAXN];void hungary() { int res = 0; memset(linker, -1, sizeof(linker)); for (int u = 1; u <= r; u++) { memset(used, false, sizeof(used)); if (dfs(u)) res++; } if (res != r) { printf("NO\n"); return; } for (int i = 1; i <= c; i++) printf("%d%c", linker[i] != -1 ? linker[i] : save[i], i == c ? '\n' : ' '); }int main() { int cas; scanf("%d", &cas); while (cas--) { scanf("%d%d", &r, &c); for (int i = 1; i <= r; i++) g[i].clear(); int pos; for (int i = 1; i <= c; i++) { for (int j = 0; j < 2; j++) { scanf("%d", &pos); save[i] = pos; g[pos].push_back(i); } } hungary(); } return 0;}