记录编号	545079	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[SYOI 2018] 消消乐	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	1.694 s
提交时间	2019-10-25 18:10:22	内存使用	3.66 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int use[2001],pre[2001],fpre[2001];
vector<int> b[4001];
//int xv[200001],yv[200001];
bool visx[2001],visy[2001];
int n,m,cnt,nx,ny,ans,cx,cy,ansx,ansy;
char xs;
struct PE
{
	int x,y;
};
PE Point[100001];
bool DFS(int x)
{
	for(int sd=0;sd<b[x].size();sd++)
	{
		int i=b[x][sd];
		if(use[i]==0)
		{
			use[i]=x;
			if(pre[i]==0||DFS(pre[i]))
			{
				pre[i]=x;
				fpre[x]=i;
				return 1;
			}
		}
	}
	return 0;
}
void JL(int x)
{
	visx[x]=1;
	ansx--;
	for(int sd=0;sd<b[x].size();sd++)
	{
			int i=b[x][sd];
			if(!visy[i])
			{
				visy[i]=1;
				ansy++;
				if(!visx[pre[i]])
					JL(pre[i]);
			}
	}
}
int LINYIN()
{
	freopen("eli.in", "r", stdin);
    freopen("eli.out", "w", stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>xs;
			if(xs=='*')
			{
				/*Point[++cnt].x=i;
				Point[cnt].y=j;
				xv[cnt]=i;
				yv[cnt]=j;*/
				b[i].push_back(j); 
				//G[i][j]=1;
			}
		}
	}
	nx=n,ny=m;
	/*sort(xv+1,xv+1+cnt);
	sort(yv+1,yv+1+cnt);
	nx=unique(xv+1,xv+1+cnt)-xv;
	ny=unique(yv+1,yv+1+cnt)-yv;*/
	/*for(int i=1;i<=cnt;i++)
	{
		int tx=Point[i].x;
		//tx=lower_bound(xv+1,xv+1+nx,tx)-xv;
		int ty=Point[i].y;
		//ty=lower_bound(yv+1,yv+1+ny,ty)-yv;
		G[tx][ty]=1;
	}*/
	for(int i=1;i<=nx;i++)
	{
		memset(use,0,sizeof(use));
		if(DFS(i))
			ans++;
	}
	ansx=nx;
	for(int i=1;i<=nx;i++)
	{
		if(fpre[i]==0)
		{
			JL(i);
		}
	}
	printf("%d\n%d ",ans,ansx);
	for(int i=1;i<=nx;i++)
	{
		if(!visx[i])
		{
			printf("%d ",i);
		}
	}
	printf("\n%d",ansy);
	for(int i=1;i<=ny;i++)
	{
		if(visy[i])
		{
			printf(" %d ",i); 
		}
	}
	return 0;
}
int LWH=LINYIN();
int main()
{
	;
}