题目大意
给定$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; }