Tag: Tarjan

题目大意

给定$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;
}