loj2057 「TJOI / HEOI2016」游戏

记横联通是一块横着的没有硬石头的地，把他们编号。竖联通同理。

对于一个空地，将其横联通编号和竖联通编号连边，二分图匹配，最大匹配为答案。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

using namespace std;

int n, m, hr[55][55], sr[55][55], hcnt, scnt, hea[5005], cnt, yy, tt, lev[5005];

int maxFlow, cur[5005];

const int oo=0x3f3f3f3f;

char ss[55][55];

queue<int> d;

struct Edge{

	int too, nxt, val;

}edge[10005];

void add_edge(int fro, int too, int val){

	edge[cnt].nxt = hea[fro];

	edge[cnt].val = val;

	edge[cnt].too = too;

	hea[fro] = cnt++;

}

void addEdge(int fro, int too, int val){

	add_edge(fro, too, val);

	add_edge(too, fro, 0);

}

bool bfs(){

	memset(lev, 0, sizeof(lev));

	lev[yy] = 1;

	d.push(yy);

	while(!d.empty()){

		int x=d.front();

		d.pop();

		for(int i=hea[x]; i!=-1; i=edge[i].nxt){

			int t=edge[i].too;

			if(!lev[t] && edge[i].val>0){

				lev[t] = lev[x] + 1;

				d.push(t);

			}

		}

	}

	return lev[tt]!=0;

}

int dfs(int x, int lim){

	if(x==tt)	return lim;

	int addFlow=0;

	for(int &i=cur[x]; i!=-1; i=edge[i].nxt){

		int t=edge[i].too;

		if(lev[t]==lev[x]+1 && edge[i].val){

			int tmp=dfs(t, min(lim-addFlow, edge[i].val));

			edge[i].val -= tmp;

			edge[i^1].val += tmp;

			addFlow += tmp;

			if(addFlow==lim)	break;

		}

	}

	return addFlow;

}

void dinic(){

	while(bfs()){

		for(int i=yy; i<=tt; i++)	cur[i] = hea[i];

		maxFlow += dfs(yy, oo);

	}

}

int main(){

	cin>>n>>m;

	for(int i=1; i<=n; i++)

		scanf("%s", ss[i]+1);

	for(int i=1; i<=n; i++)

		for(int j=1; j<=m; j++)

			if(!hr[i][j] && ss[i][j]!='#'){

				hcnt++;

				for(int k=j; k<=m && ss[i][k]!='#'; k++)

					hr[i][k] = hcnt;

			}

	for(int i=1; i<=n; i++)

		for(int j=1; j<=m; j++)

			if(!sr[i][j] && ss[i][j]!='#'){

				scnt++;

				for(int k=i; k<=n && ss[k][j]!='#'; k++)

					sr[k][j] = scnt;

			}

	memset(hea, -1, sizeof(hea));

	for(int i=1; i<=n; i++)

		for(int j=1; j<=m; j++)

			if(ss[i][j]=='*')

				addEdge(hr[i][j], hcnt+sr[i][j], 1);

	yy = 0; tt = hcnt + scnt + 1;

	for(int i=1; i<=hcnt; i++)

		addEdge(yy, i, 1);

	for(int i=1; i<=scnt; i++)

		addEdge(i+hcnt, tt, 1);

	dinic();

	cout<<maxFlow<<endl;

	return 0;

}