Solution [COCI 2020.3]Skandi

题目大意：给定一个 (n) 行 (m) 列的填数游戏，每个问题可以向右或者向下，求出填完表格最少需要回答的问题数

二分图最大点独立集

分析：

文中把原矩阵中 (1) 和 (0) 分别称为黑点和白点

那么我们考虑每一个白点，如果要覆盖它，那么最靠近它的，它左边和上面的黑点至少有一个要被选中。

问题变成了，给定 (n) 个要求，每个要求为 ((a,b)) 两点中至少有一个点要被选中，求最少选中多少个点可以满足所有要求。

发现每个要求的两个点对应的方向都不一样，因此我们将一个黑点拆成两个，分别对应右方和下方，白点的要求即为二分图中的边，我们要求的即为二分图的最小点覆盖。

答案为最大匹配，我们还要输出方案

关于二分图最小点独立集输出方案，可以参考我以前写的博客

由于这篇博客貌似是初二的时候写的，极为混乱所以在这儿再写一下qaq，可以结合食用

假设我们只考虑匹配边，将左右两侧的点集记为 (X,Y)，那么需要选择点可以分为以下几种情况

1.在 (X) 点集里面的，出度大于 (1) 的点
2.在 (Y) 点集里面的，入度大于 (1) 的点
3.一条边的两个点度数都为 (1) ，这个时候我们可以随便选

证明显然。我们从源点开始 (dfs)，只走没有满流的边（反向弧也可以走），标记可以到达的所有点。那么 (X) 点集中所有没有被标记的点，和 (Y) 点集中所有标记了的点就是我们要的答案。

证明：

对于 (X) 点集，如果它没有被标记，那么从源点到它的边一定满流，对应情况1,3

对于 (Y) 点集，如果它被标记了，说明与它相连的边有边没有满流（那么它的的度数大于 (1) ），这个时候我们需要选择该点。(dfs)也会沿着没有满流的反向弧（对应匹配边）标记在 (X) 点集中的点，避免重复计算

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 512;
namespace dinic{
	const int maxn = 1e6,maxm = 1e7;
	struct edge{int u,v,cap;}edges[maxm];
	int head[maxn],nxt[maxm],tot = 1;
	inline void addedge(int u,int v,int cap){
		edges[++tot] = edge{u,v,cap};
		nxt[tot] = head[u];
		head[u] = tot;
		edges[++tot] = edge{v,u,0};
		nxt[tot] = head[v];
		head[v] = tot;
	}
	int d[maxn];
	inline bool bfs(int s,int t){
		memset(d,-1,sizeof(d));
		d[s] = 0;
		static queue<int> q;
		q.push(s);
		while(!q.empty()){
			int u = q.front();q.pop();
			for(int i = head[u];i;i = nxt[i]){
				const edge &e = edges[i];
				if(e.cap && d[e.v] == -1){
					d[e.v] = d[u] + 1;
					q.push(e.v);
				}
			}
		}
		return d[t] != -1;
	}
	int cur[maxn];
	inline int dfs(int u,int a,int t){
		if(u == t || !a)return a;
		int res = 0,f;
		for(int &i = cur[u];i;i = nxt[i]){
			const edge &e = edges[i];
			if((d[u] + 1 == d[e.v]) && (f = dfs(e.v,min(a,e.cap),t)) > 0){
				res += f;
				a -= f;
				edges[i].cap -= f;
				edges[i ^ 1].cap += f;
				if(!a)break;
			}
		}
		return res;
	}
	inline int maxflow(int s,int t){
		int res = 0;
		while(bfs(s,t)){
			memcpy(cur,head,sizeof(cur));
			res += dfs(s,0x7fffffff,t);
		}
		return res;
	}
	int vis[maxn];
	inline void dfs(int u){
		vis[u] = 1;
		for(int i = head[u];i;i = nxt[i]){
			const edge &e = edges[i];
			if(vis[e.v] || !e.cap)continue;
			dfs(e.v);
		}
	}
}
struct pos{int x,y;};
vector<pos> black;
char mp[maxn][maxn];
int n,m,l[maxn][maxn],up[maxn][maxn];
inline pos getpos(int x){
	printf("GETPOS:%d
",x);
	fflush(stdout);
	pos res;
	res.x = (x + m - 1) / m;
	res.y = x - (res.x - 1) * m;
	return res;
}
inline int getid(int x,int y){return (x - 1) * m + y;}
inline int getid(pos now){return getid(now.x,now.y);}
inline void findright(int from,pos now){
	while(true){
		now.y++;
		if(mp[now.x][now.y] != '0')break;
		dinic::addedge(from,getid(now.x,now.y),1);
	}
}
inline void finddown(int from,pos now){
	while(true){
		now.x++;
		if(mp[now.x][now.y] != '0')break;
		dinic::addedge(from,getid(now.x,now.y),1);
	}
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= n;i++)scanf("%s",mp[i] + 1);
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
			if(mp[i][j] == '1')black.push_back(pos{i,j});
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
			if(mp[i][j - 1] == '1')l[i][j] = getid(i,j - 1);
			else l[i][j] = l[i][j - 1];
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
			if(mp[i - 1][j] == '1')up[i][j] = getid(i - 1,j);
		else up[i][j] = up[i - 1][j];
	int ss = n * m * 2 + 1,tt = ss + 1;
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
			if(mp[i][j] == '0')
				dinic::addedge(l[i][j],up[i][j] + n * m,1);
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
			if(mp[i][j] == '1')dinic::addedge(ss,getid(i,j),1),dinic::addedge(n * m + getid(i,j),tt,1);
	printf("%d
",dinic::maxflow(ss,tt));
	dinic::dfs(ss);
	for(int x = 1;x <= n;x++)
		for(int y = 1;y <= m;y++)
			if(mp[x][y] == '1'){
				int a = getid(x,y),b = n * m + a;
				if(!dinic::vis[a])printf("%d %d DESNO
",x,y);
				if(dinic::vis[b])printf("%d %d DOLJE
",x,y);
			}
	return 0;
}