题解：P10940 舞动的夜晚

· · 题解

省流：二分图最大匹配的必不经边。即：任意最大匹配都不会用到的边。因此但凡用了这条边，一定不会有最大匹配。因此与题意等价。

本篇题解会顺带讲解必经边，非必经边，必不经边的判定方法，其实都是统一的。

首先用网络流随便搞出一个最大匹配以及他的残量网络。

众所周知，我们可以在原图中找到一条增广路（可以经过一端是源点或者汇点的边），并反转这条路径上的所有边的状态（匹配 \to 不匹配 或 不匹配 \to 匹配）使得反转后仍然是一个匹配。

在最大匹配中，不存在源点到汇点的增广路。想要改变某条边 (u,v) 的状态（假设此时 1 流量的方向是 u \to v），只能尝试寻找 v \rightsquigarrow u 的一条增广路。如果能找到，那么这条边的状态可以被反转。同时 u\to v \rightsquigarrow u 会形成一个环，所以整张图流量不变，反转后仍然是一个最大匹配。反之，若找不到，则一定不能被反转。

稍加思考可以发现，如果我们把图上的所有边按照 1 流量的方向定向，那么 u \to v 可反转，等价于 u 和 v 在定向后的有向图中属于同一个强连通分量。反之亦然，即不可反转，等价于 u 和 v 在定向后的有向图中不属于同一个强连通分量。

因此，定向完以后跑一遍 tarjan，我们就可以判断每一条边的状态是否可以改变，其中：

至此，求法结束。

总结一下流程：

  1. 跑一遍网络流，求出残量网络。
  2. 把所有边按照 1 流量方向定向，在新有向图上跑 tarjan 求强连通分量。
  3. 枚举所有边，判断其两端点是否在同一个强连通分量中。

而对于此题，我们只需要找出不能反转的非匹配边即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,a,b) for(int i=a;i<=b;i++)
inline ll rd() {
    ll x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    return x*f;
}
#define d rd()
#define pb push_back
struct edge{ll u,v,w,id,nx;}e[2000010];
ll cnt=1,hd[1000010];
void add(ll u,ll v,ll w,ll id){e[++cnt]={u,v,w,id,hd[u]};hd[u]=cnt;}
void ad(ll u,ll v,ll w,ll id){add(u,v,w,id),add(v,u,0,id);}
ll n,m,S,T,nodes;
ll cur[1000010];
ll dep[1000010];
#define inf 0x3f3f3f3f3f3f3f3f
queue<ll>q;
bool bfs(){
    f(i,1,nodes)dep[i]=inf,cur[i]=hd[i];
    dep[S]=0;while(!q.empty())q.pop();
    q.push(S);while(!q.empty()){
        ll u=q.front();q.pop();
        for(int i=hd[u];i;i=e[i].nx){
            ll v=e[i].v;if(!e[i].w)continue;
            if(dep[v]==inf){
                dep[v]=dep[u]+1,q.push(v);
                if(v==T)return 1;
            }
        }
    }return 0;
}ll dfs(ll u,ll fl){
    if(u==T)return fl;
    ll sum=0;for(int i=cur[u];i&&fl;i=e[i].nx){
        ll v=e[i].v;cur[u]=i;if(!e[i].w||dep[v]!=dep[u]+1)continue;
        ll k=dfs(v,min(fl,e[i].w));
        fl-=k,sum+=k,e[i].w-=k,e[i^1].w+=k;
    }return sum;
}ll dinic(){
    ll res=0;while(bfs())res+=dfs(S,inf);
    return res;
}
ll dfn[100010],low[100010],tim;
ll bel[100010],scc;
ll st[100010],tp;
bool ins[100010];
vector<ll> E[100010];
void dfs(ll u){
    dfn[u]=low[u]=++tim;
    st[++tp]=u,ins[u]=1;
    for(auto v:E[u]){
        if(!dfn[v])dfs(v),low[u]=min(low[u],low[v]);
        else if(ins[v])low[u]=min(low[u],dfn[v]);
    }if(low[u]==dfn[u]){
        scc++;ll now;while(1){
            now=st[tp--];
            ins[now]=0,bel[now]=scc;
            if(now==u)break;
        }
    }
}
bool is[100010];
int main(){
    n=d,m=d;S=n+m+1,T=nodes=S+1;
    f(i,1,n)ad(S,i,1,0);
    f(i,1,m)ad(i+n,T,1,0);
    ll M=d;f(i,1,M){
        ll u=d,v=d;
        ad(u,v+n,1,i);
    }dinic();
    f(i,2,cnt)if(e[i].w==1){
        ll u=e[i].u,v=e[i].v;
        // if(u==S||u==T||v==S||v==T)continue;
        E[u].pb(v);
    }f(i,1,nodes)if(!dfn[i])dfs(i);
    ll res=0;
    f(i,2,cnt)if(e[i].w==1&&(i%2==0)){
        ll u=e[i].u,v=e[i].v;
        if(u==S||u==T||v==S||v==T)continue;
        // cout<<u<<" "<<v<<endl;
        if(bel[u]!=bel[v])is[e[i].id]=1,res++;
    }cout<<res<<endl;
    f(i,1,M)if(is[i])cout<<i<<" ";
    return 0;
}