P16312

Nightsky_Stars · 2026-04-24 17:28:37 · 题解

题意：

给定一个平衡二分图，要求添加恰好一条边，使得最大匹配数增加，求符合条件的边的方案数。

思路：

一眼网络流。先跑一遍最大流，考虑跑完最大流后残余网络，此时已经不存在增广路。思考一下，如果添加一条边 (u,v) 可以使得流量变大，那就相当于从源点到 u 到 v 再到汇点都还有连通的有容量的边。

我们从源点和汇点用 bfs 找到所有符合要求的左右部点数量相乘即可。

总复杂度 O(m\sqrt{n})。

CODE:

#include<bits/stdc++.h>
#define file(str) freopen(str".in","r",stdin),freopen(str".out","w",stdout)
using namespace std;
typedef long long ll;
const int N=5e5+10,inf=1e9;
struct node{
    int x,id;
    ll w;
};
struct edge{
    int u,v;
}a[N];
int now[N],d[N],n,m,s,t,l[N],r[N];
bool vis[N];
vector<int> g[N];
vector<node> e[N];
void add(int u,int v,ll w){
    e[u].push_back({v,e[v].size(),w});
    e[v].push_back({u,e[u].size()-1,0});
}
bool bfs(){
    memset(d,0,sizeof(d));
    queue<int> q;
    q.push(s);
    d[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(auto x:e[u]){
            int v=x.x;
            ll w=x.w;
            if(d[v]==0&&w){
                d[v]=d[u]+1;
                q.push(v);
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
ll dfs(int u,ll c){
    if(u==t) return c;
    ll s=0;
    for(int i=now[u];i<e[u].size()&&c;i++){
        now[u]=i;
        int v=e[u][i].x;
        ll w=e[u][i].w;
        if(d[u]+1==d[v]&&w){
            ll k=dfs(v,min(c,w));
            e[u][i].w-=k;
            e[v][e[u][i].id].w+=k;
            s+=k;
            c-=k;
        }
    }
    if(s==0) d[u]=0;
    return s;
}
ll dinic(){
    ll res=0;
    while(bfs()){
        memset(now,0,sizeof(now));
        res+=dfs(s,inf);
    }
    return res;
}
ll bfs(int o){
    queue<int> q;
    for(int i=1;i<=2*n;i++){
        g[i].clear();
        vis[i]=0;
    }
    if(!o){
        for(int i=1;i<=m;i++){
            if(l[a[i].u]==a[i].v) g[a[i].v+n].push_back(a[i].u);
            else g[a[i].u].push_back(a[i].v+n);
        }
        for(int i=1;i<=n;i++){
            if(l[i]==0){
                vis[i]=1;
                q.push(i);
            }
        }
    }else{
        for(int i=1;i<=m;i++){
            if(l[a[i].u]==a[i].v) g[a[i].u].push_back(a[i].v+n);
            else g[a[i].v+n].push_back(a[i].u);
        }
        for(int i=1;i<=n;i++){
            if(r[i]==0){
                vis[i+n]=1;
                q.push(i+n);
            }
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(auto v:g[u]){
            if(vis[v]) continue;
            vis[v]=1;
            q.push(v);
        }
    }
    ll c=0;
    if(!o){
        for(int i=1;i<=n;i++){
            if(vis[i]) c++;
        }
    }else{
        for(int i=n+1;i<=2*n;i++){
            if(vis[i]) c++;
        }
    }
    return c;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        cin>>n>>m;
        s=0;
        t=2*n+1;
        for(int i=0;i<=2*n+1;i++){
            e[i].clear();
            g[i].clear();
            d[i]=l[i]=r[i]=vis[i]=0;
        }
        for(int i=1;i<=n;i++){
            add(s,i,1);
            add(i+n,t,1);
        }
        for(int i=1;i<=m;i++){
            int u,v;
            cin>>u>>v;
            a[i]={u,v};
            add(u,v+n,1);
        }
        ll ans=dinic();
        if(ans==n){
            cout<<"0\n";
            continue;
        }
        for(int i=1;i<=n;i++){
            for(auto [x,id,w]:e[i]){
                if(x>n&&x<=2*n&&w==0){
                    l[i]=x-n;
                    r[x-n]=i;
                    break;
                }
            }
        }
        cout<<bfs(0)*bfs(1)<<"\n";
    }
    return 0;
}