C++14(g++5.4) 解法, 执行用时: 146ms, 内存消耗: 1120K, 提交时间: 2018-11-02 21:13:25

#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
char str[2005];
int k, n, m, visx[2005], visy[2005], L[2005], R[2005];
vector<int> G[2005], F;
int Sech(int x)
{
	int i, v;
	visx[x] = 1;
	for(i=0;i<G[x].size();i++)
	{
		v = G[x][i];
		if(visy[v]==0)
		{
			visy[v] = 1;
			if(R[v]==-1 || Sech(R[v]))
			{
				R[v] = x, L[x] = v;
				return 1;
			}
		}
	}
	return 0;
}
int main(void)
{
	int i, j, ans;
	scanf("%d%d", &n, &m);
	for(i=1;i<=n;i++)
	{
		scanf("%s", str+1);
		for(j=1;j<=m;j++)
		{
			if(str[j]=='*')
				G[i].push_back(j);
		}
	}
	ans = 0;
	memset(L, -1, sizeof(L));
	memset(R, -1, sizeof(R));
	for(i=1;i<=n;i++)
	{
		memset(visy, 0, sizeof(visy));
		if(Sech(i))
			ans++;
	}
	memset(visx, 0, sizeof(visx));
	memset(visy, 0, sizeof(visy));
	printf("%d\n", ans);
	for(i=1;i<=n;i++)
	{
		if(L[i]==-1)
			Sech(i);
	}
	for(i=1;i<=n;i++)
	{
		if(visx[i]==0)
			F.push_back(i);
	}
	printf("%d", F.size());
	for(i=0;i<F.size();i++)
		printf(" %d", F[i]);
	puts("");
	F.clear();
	for(i=1;i<=m;i++)
	{
		if(visy[i])
			F.push_back(i);
	}
	printf("%d", F.size());
	for(i=0;i<F.size();i++)
		printf(" %d", F[i]);
	puts("");
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 183ms, 内存消耗: 1376K, 提交时间: 2018-11-02 19:57:16

#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
const int N=2005;
int n,m,res,cnt,head[N],vis[N],match[N],mk[N],mk2[N],r[N],c[N]; char s[N];
struct edge{int to,nxt;}e[200005];
void adde(int x,int y){e[++cnt].to=y; e[cnt].nxt=head[x]; head[x]=cnt;}
bool dfs(int u){
	for (int i=head[u],v;i;i=e[i].nxt)
		if (v=e[i].to,!vis[v]){
			vis[v]=1;
			if (!match[v]||dfs(match[v])) return match[v]=u,mk[u]=1,1;
		}
	return 0;
}
void dfs2(int u){
	for (int i=head[u],v;i;i=e[i].nxt)
		if (v=e[i].to,!mk2[v]){
			mk2[v]=1;
			dfs2(match[v]);
		}
}
int main(){
	scanf("%d%d",&n,&m);
	rep (i,1,n){
		scanf("%s",s+1);
		rep (j,1,m) if (s[j]=='*') adde(i,j);
	}
	rep (i,1,n){
		memset(vis,0,sizeof(vis));
		if (dfs(i)) res++;
	}
	printf("%d\n",res);
	rep (i,1,n) if (!mk[i]) dfs2(i);
	rep (i,1,m) if (match[i]) if (mk2[i]) c[++*c]=i; else r[++*r]=match[i];
	sort(r+1,r+1+*r); sort(c+1,c+1+*c);
	printf("%d",*r); rep (i,1,*r) printf(" %d",r[i]); puts("");
	printf("%d",*c); rep (i,1,*c) printf(" %d",c[i]); puts("");
	return 0;
}