题目大意
给定$n(n \le 300)$个外星人,给定$m(m \le 1500)$个地球人,再给定任意地球人与外星人的关系
关系由一个$nm$的0/1
矩阵给出,表示第$i$个外星人是否能与第$j$个地球人配对
要求每个外星人至少与一个地球人配对,地球人只能与至多一个外星人匹配
问由哪些关系一定不可能出现在合法的匹配方案中
解题报告
这是一道基础图论题
我们可以先来考虑一个简单的版本:地球人个数与外星人一样
那么我们可以先用二分图匹配跑一个完备匹配出来
此时在匹配中的边一定可以出现在合法的匹配方案中
只考虑不在当前匹配中的边,那么一定是走一条像增广路一样的东西
就是一条匹配边,一条非匹配边交叉着走。最后走一个偶环绕回来
于是我们对于从左边连到右边的边,只保留非匹配边
对于从右到左的边,我们只保留匹配边。这样就可以保证是偶环了
至于能不能走回来,我们发现这就是一个有向图的强连通分量
于是我们再跑一个Tarjan,判断一下就可以了
现在考虑地球人与外星人不等的情况
我们可以把外星人补到与地球人一样多啊!
就是加一些可以与所有地球人匹配的外星人就可以了
当然不加点,大力讨论一波也是可以的
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 3009;
const int M = N * N << 1;
const int INF = 1e9;
int head[N],nxt[M],to[M],flow[M],low[N],dfs[N];
int n,m,S,T,E=1,mth[N],id[N][N],num[N],ins[N]; char pat[N];
stack<int> stk;
inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
inline int AddEdge(int u, int v, int f=0) {
if (f) {
to[++E] = v; nxt[E] = head[u]; head[u] = E;
to[++E] = u, nxt[E] = head[v], head[v] = E;
flow[E - 1] = f; return E - 1;
} else to[++E] = v, nxt[E] = head[u], head[u] = E;
}
class Network_Flow{
int dis[N],cur[N]; queue<int> que;
public:
inline int MaxFlow() {
int ret = 0;
while (BFS()) {
memcpy(cur,head,sizeof(cur));
ret += DFS(S, INF);
} return ret;
}
private:
int DFS(int w, int f) {
if (w == T) return f; int ret = 0;
for (int &i=cur[w],tmp;i;i=nxt[i]) {
if (flow[i] && dis[to[i]] == dis[w] + 1) {
tmp = DFS(to[i], min(f, flow[i]));
flow[i] -= tmp; flow[i^1] += tmp;
f -= tmp; ret += tmp;
if (!f) return ret;
}
} return ret;
}
inline bool BFS() {
memset(dis,60,sizeof(dis));
dis[S] = 0; que.push(S);
while (!que.empty()) {
int w = que.front(); que.pop();
for (int i=head[w];i;i=nxt[i]) {
if (flow[i] && dis[to[i]] > INF) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
} return dis[T] < INF;
}
}Dinic;
void Tarjan(int w) {
static int dfs_cnt = 0, scc_cnt = 0;
dfs[w] = low[w] = ++dfs_cnt; stk.push(w); ins[w] = 1;
for (int i=head[w];i;i=nxt[i]) {
if (!dfs[to[i]]) Tarjan(to[i]), low[w] = min(low[w], low[to[i]]);
else if (ins[to[i]]) low[w] = min(low[w], dfs[to[i]]);
}
if (low[w] == dfs[w]) {
for (scc_cnt++;!stk.empty();stk.pop()) {
num[stk.top()] = scc_cnt; ins[stk.top()] = 0;
if (stk.top() == w) {stk.pop(); break;}
}
}
}
int main() {
n = read(); m = read(); S = 0; T = N - 1;
memset(id, -1, sizeof(id));
for (int i=1;i<=n;i++) {
scanf("%s",pat+1);
for (int j=1;j<=m;j++) {
if (pat[j] == '1') {
id[i][j] = AddEdge(i, m + j, 1);
}
}
}
for (int i=1;i<=n;i++) AddEdge(S, i, 1);
for (int i=1;i<=m;i++) AddEdge(m + i, T, 1);
if (Dinic.MaxFlow() != n) {
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) putchar('1');
puts("");
}
} else {
E = 1; memset(head,0,sizeof(head));
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++)
if (~id[i][j] && !flow[id[i][j]]) {mth[j] = i; break;}
for (int i=n+1,j=1;i<=m;i++,j++) {while(mth[j])j++;mth[j]=i;}
for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) if (~id[i][j] || i > n) {
if (mth[j] == i) AddEdge(m+j, i); else AddEdge(i, m+j);}
for (int i=1;i<=m*2;i++) if (!dfs[i]) Tarjan(i);
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if ((~id[i][j]) && (mth[j] == i || num[i] == num[m+j])) putchar('0');
else putchar('1');
} putchar('\n');
}
}
return 0;
}