边数为白点的个数，左部点为黑点的个数，则时间复杂度为 \(O(nm\sqrt{nm})\) ，即 \(O(n^{\frac{3}{2}}m^{\frac{3}{2}})\) ，本题的 \(n\) ， \(m\) 均小于 \(500\) ，大概能够在 \(1s\) 内求出答案。
C++代码 #include <queue> #include <cstdio> #include <vector> #include <cstring> #include <iostream> using namespace std; #define INF 0x3f3f3f3f const int MAXN = 1e6 + 5; const int MAXM = 5e2 + 5; struct Node { int to, val, rev;//依次为：下一个点，边的容量，相反的边的编号 Node() {} Node(int T, int V, int R) { to = T; val = V; rev = R; } }; vector<Node> v[MAXN];//用vector存图的癖好... int dn[MAXN], rt[MAXN];//预处理白色点可以右那两个点扩展而来 queue<int> q; int de[MAXN], be[MAXN]; int twin[MAXN]; bool vis[MAXN]; int n, m, s, t; int arr[MAXM][MAXM]; bool bfs() {//将残量网络分层 bool flag = 0; memset(de, 0, sizeof(de)); while(!q.empty()) q.pop(); q.push(s); de[s] = 1; be[s] = 0; while(!q.empty()) { int now = q.front(); q.pop(); int SIZ = v[now].size(); for(int i = 0; i < SIZ; i++) { int next = v[now][i].to; if(v[now][i].val && !de[next]) { q.push(next); be[next] = 0; de[next] = de[now] + 1; if(next == t) flag = 1; } } } return flag; } int dfs(int now, int flow) {//沿着增广路增广 if(now == t || !flow) return flow; int i, surp = flow; int SIZ = v[now].size(); for(i = be[now]; i < SIZ && surp; i++) { be[now] = i; int next = v[now][i].to; if(v[now][i].val && de[next] == de[now] + 1) { int maxnow = dfs(next, min(surp, v[now][i].val)); if(!maxnow) de[next] = 0; v[now][i].val -= maxnow; v[next][v[now][i].rev].val += maxnow; surp -= maxnow; } } return flow - surp; } int Dinic() {//网络最大流，亦可用于二分图匹配 int res = 0; int flow = 0; while(bfs()) while(flow = dfs(s, INF)) res += flow; return res; } int GetHash(int i, int j) {//获取点的编号 return (i - 1) * m + j; } void Down(int now, int i, int j) {//黑点向下扩展，每个白点最多遍历到一次 if(i != now) dn[GetHash(now, j)] = GetHash(i, j); if(arr[now + 1][j] == 2) Down(now + 1, i, j); } void Right(int now, int i, int j) { //黑点向右扩展，每个白点最多遍历到一次 if(j != now) rt[GetHash(i, now)] = GetHash(i, j) + n * m; if(arr[i][now + 1] == 2) Right(now + 1, i, j); } void GetMin(int now) {//dfs求构造方式 vis[now] = true; int SIZ = v[now].size(); for(int i = 0; i < SIZ; i++) { int next = v[now][i].to; if(vis[next] || !v[now][i].val) continue; GetMin(next); } } int main() { scanf("%d %d", &n, &m); s = 0; t = 2 * n * m + 1;//源点和汇点初始化 char ch; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> ch; if(ch == '1') arr[i][j] = 1; else arr[i][j] = 2; } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(i == 1 && j == 1) continue; if(arr[i][j] == 1) {//向右或向下扩展，一个白点会被访问2次 Down(i, i, j); Right(j, i, j); } } } for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { if(arr[i][j] == 1) {//源点到左部点，汇点到右部点连边 int now = GetHash(i, j); int idnow = v[now].size(); int ids = v[s].size(); v[s].push_back(Node(now, 1, idnow)); v[now].push_back(Node(s, 0, ids)); now = GetHash(i, j) + n * m; idnow = v[now].size(); int idt = v[t].size(); v[now].push_back(Node(t, 1, idt)); v[t].push_back(Node(now, 0, idnow)); } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(i == 1 && j == 1) continue; if(arr[i][j] == 1) continue; int A = dn[GetHash(i, j)];//左部点到右部点连边 int B = rt[GetHash(i, j)]; int idA = v[A].size(); int idB = v[B].size(); v[A].push_back(Node(B, 1, idB)); v[B].push_back(Node(A, 0, idA)); } } printf("%d\n", Dinic()); GetMin(s); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(arr[i][j] == 2) continue; if(!vis[GetHash(i, j)])//打印答案 printf("%d %d DOLJE\n", i, j); if(vis[GetHash(i, j) + n * m]) printf("%d %d DESNO\n", i, j); } } return 0; }