题解：P10940 舞动的夜晚

· · 题解

本题让我们求二分图的不可行边。

先跑一遍 dinic 求出二分图最大匹配，接下来考虑必须边（一定存在于最大匹配中的边）、可行边（有可能存在于最大匹配中的边）和不可行边（不能存在于最大匹配中的边，这道题的答案，可行边的补集）的判断条件。

如果匹配边从右向左建有向边，非匹配边从左向右建匹配边，我们可以发现，u 和 v 间存在增广路等价于存在一条 u\leadsto v 的路径。

必须边

若 (u,v) 是匹配边，且不存在路径 u\leadsto v，因为如果存在的话，v\to u 和 u\leadsto v 构成环，全部取反可以得到另一组最大匹配，此时 (u,v) 不是匹配边，不符合必须边的定义。

可行边

若 (u,v) 是匹配边，那么它一定是可行边。

若 (u,v) 在一个环上，那么这个环全部取反可以获得包含 (u,v) 的一组最大匹配，也是可行边。

容易发现必须边是可行边的子集。

不可行边

可行边的补集。

关于判断 (u,v) 是否在一个环上，可以用 Tarjan 求强连通分量解决。

故本题流程如下：

  1. dinic 求最大匹配，建立流量为 1 的边（符合上述有向图定义）。
  2. 在这张图上作 Tarjan 求 SCC。
  3. 枚举所有边，找出不可行边。
  4. 输出这些边的输入编号。
#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e4+10;
const int inf=0x3f3f3f3f;

int n,m,t,cur[MAXN<<1],dep[MAXN<<1];
int S,T;

int dfn[MAXN<<1],low[MAXN<<1],dfscnt,id[MAXN<<1],sc;

bool vis[MAXN<<1];
stack<int> st;

struct edge{
    int to,w,id;
};

vector<edge> e[MAXN<<1];
vector<int> new_e[MAXN<<1];

bool bfs(){
    memset(dep,-1,sizeof dep);
    queue<int> q;
    q.push(S);
    dep[S]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<e[u].size();i++){
            int v=e[u][i].to,w=e[u][i].w;
            if(dep[v]==-1&&w){
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[T]!=-1;
}

int dfs(int u,int limit){
    if(u==T)return limit;
    for(int i=cur[u];i<e[u].size();i++){
        cur[u]=i;
        int v=e[u][i].to,w=e[u][i].w;
        if(dep[v]==dep[u]+1&&w){
            int ret=dfs(v,min(w,limit));
            if(ret){
                e[u][i].w-=ret;
                e[v][e[u][i].id].w+=ret;
                return ret;
            }else dep[v]=-1;
        }
    }
    return 0;
}

void add(int u,int v){ // 神秘vector做法
    int ui=e[u].size();
    int vi=e[v].size();
    e[u].push_back({v,1,vi});
    e[v].push_back({u,0,ui});
}

void tarjan(int u){
    dfn[u]=low[u]=++dfscnt;
    vis[u]=1;
    st.push(u);
    for(int v:new_e[u]){
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(vis[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        int x;
        sc++;
        do{
            x=st.top();
            st.pop();
            vis[x]=0;
            id[x]=sc;
        }while(x!=u);
    }
}

map<int,int> ma[MAXN];
vector<int> _ans;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>t;
    S=0,T=n+m+1;
    for(int i=1,x,y;i<=t;i++){
        cin>>x>>y;y+=n;
        add(x,y);
        ma[x][y]=i;
    }
    for(int i=1;i<=n;i++)add(S,i);
    for(int i=n+1;i<=n+m;i++)add(i,T);
    int ans=0,flow;
    while(bfs()){ // dinic
        memset(cur,0,sizeof cur);
        while(flow=dfs(S,inf))ans+=flow;
    }
    for(int u=0;u<=T;u++){
        for(auto [v,w,id]:e[u]){
            if(w>0)new_e[u].push_back(v); // 建立流量为1的边 
            if(e[v][id].w>0)new_e[v].push_back(u);
        }
    }
    for(int i=1;i<=n+m;i++) // 求SCC
        if(!dfn[i])tarjan(i);
    for(int u=1;u<=n;u++)
        for(auto [v,w,pp]:e[u])
            if(w!=0&&id[u]!=id[v]){ // 不是匹配边且u,v不在一个SCC
                if(v==0)continue;
                _ans.push_back(ma[u][v]);
            }
    cout<<_ans.size()<<'\n';
    sort(_ans.begin(),_ans.end());
    for(int i:_ans)cout<<i<<' ';
    cout<<'\n';
    return 0;
}