自动搬运

查看原文

来自洛谷，原作者为

	jimmywang 基环内向树，二维前缀和，三碳化四铝，闪电五连鞭

搬运于2025-08-24 23:02:44，当前版本为作者最后更新于2024-12-15 22:36:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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

众所周知，我们可以在原图中找到一条增广路（可以经过一端是源点或者汇点的边），并反转这条路径上的所有边的状态（匹配 $\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，我们就可以判断每一条边的状态是否可以改变，其中：

• 若一条匹配边 $(u,v)$ （$u$ 左 $v$ 右）不可被反转，那么这是一条 必经边；否则是非必经边。

• 若一条非匹配边 $(u,v)$ （$u$ 左 $v$ 右）不可被反转，那么这是一条 必不经边；否则是非必经边。

至此，求法结束。

总结一下流程：

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;
}