题目：
Description
有一天，有N个外星人企图入侵地球。地球派出全球战斗力最强的M个人代表人类对抗外星人。根据外星的战斗规则，每个外星人应该分别与一名地球人对战（不同的外星人要与不同的地球人对战）。如果任意一个外星人获胜，那么地球将被外星人占领。
幸运的是，人类可以决定对战顺序，且可以决定每次对战的两名战士，但是要保证符合外星的战斗规则。
地球有一个保护神。他能提前预知每一名地球人和每一名外星人的战斗结果。在战争开始前，保护神必须确定第一场战斗的两名战士。举个例子：假设第一场为人类A对战外星人A，但是人类A是能打败外星人B的唯一一名战士，那么即使人类A打败了外星人A，也不可避免地导致地球被外星人占领，因为外星人B将会打败他的对手。这意味着：第一场战斗中，“人类A对战外星人A”这个组合是不能选的。
你的任务是：找出所有在第一场战斗中不能选的组合，即选择该组合会不可避免地导致地球被外星人占领。
Input
第一行为两个整数 N,M(1≤N≤300,N≤M≤1500) 。
接下来N行M列是一个二进制矩阵A。 Ai,j=1 当且仅当第j个地球人能战胜第i个外星人。
Output
Sample Input
【样例输入1】
4 4
1111
1000
1111
1111
【样例输入2】
4 5
10000
10000
10000
10000
【样例输入3】
4 4
1111
1110
1100
1000
Sample Output
【样例输出1】
1000
0111
1000
1000
【样例输出2】
11111
11111
11111
11111
【样例输出3】
1110
1101
1011
0111
HINT
【数据范围与约定】
子任务1（10分）： N=4,M=6
子任务2（20分）： N=15,M=30
子任务3（25分）： N=300,M=300
子任务4（45分）： N=300,M=1500
题解：
解法：二分图最大匹配+Tarjan
首先，题意可以转化为：去掉第i行和第j列后，判断二分图是否存在满匹配。直接暴力做可以得到30分。
更进一步，就是判断边(i, j)是否为该二分图最大匹配的匹配边。
考虑n = m的情况。我们可以先跑一次最大匹配，将匹配边从左向右连，非匹配边从右向左连。对新的图跑Tarjan，若左边的点i与右边的点j处于同一个强联通分量中，边(i, j)一定是最大匹配的匹配边（理由是一个强联通分量中，必能从该点出发又回到该点，而这个路线恰好是匹配边-非匹配边-匹配边……）。
对于m > n的情况，把外星人补成m个，就可以转化为n = m的情况了。
心得：
以前匈牙利算法只会求其中一种情况，这个问题相当于求最大匹配的所有解:将两边数字同一跑匈牙利后跑tarjian；
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int M=;
int tot,fir[M],nxt[M*M],go[M*M];
int belon[M];
int n,m;
int id[M],dfs[M],low[M],stack[M],top,sumid,cnt;
bool visit[M];
bool insta[M];
char ma[M][M];
inline void comb(int u,int v)
{
nxt[++tot]=fir[u],fir[u]=tot,go[tot]=v;
}
bool find(int x)
{
for(int i=;i<=m;i++)
{
if(ma[x][i]==''&&!visit[i])
{
visit[i]=true;
if(!belon[i]||find(belon[i]))
{
belon[i]=x;
return true;
}
}
}
return false;
}
inline void tarjian(int u)
{
dfs[u]=low[u]=++cnt;
stack[++top]=u;
insta[u]=true;
for(int e=fir[u];e;e=nxt[e])
{
int v=go[e];
if(!dfs[v])
{
tarjian(v);
low[u]=min(low[u],low[v]);
}
else
if(insta[v])
low[u]=min(low[u],dfs[v]);
}
if(low[u]==dfs[u])
{
sumid++;
while(stack[top]!=u)
{
insta[stack[top]]=false;
id[stack[top]]=sumid;
top--;
}
insta[stack[top]]=false;
id[stack[top]]=sumid;
top--;
}
}
int main()
{
freopen("a.in","r",stdin);
scanf("%d%d",&n,&m); for(int i=;i<=n;i++)
scanf("%s",ma[i]+);
for(int i=n+;i<=m;i++)
for(int j=;j<=m;j++)
ma[i][j]=''; int temp=;
for(int i=;i<=n;i++)
{
memset(visit,false,sizeof(visit));
if(find(i)) temp++;
}
if(temp!=n)
{ for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
cout<<"";
cout<<endl;
}
return ;
}
else
{
int k=n+;
for(int i=;i<=m;i++)
{
if(!belon[i])
belon[i]=k++;
}
}
for(int i=;i<=m;i++)
for(int j=;j<=m;j++)
if(ma[i][j]=='')
{
if(belon[j]==i) comb(i,j+m);
else comb(j+m,i);
}
for(int i=;i<=m*;i++)
if(!dfs[i]) tarjian(i);
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(ma[i][j]==''&&(belon[j]==i||id[i]==id[j+m]))
cout<<"";
else cout<<"";
}
cout<<endl;
}
return ;
}