题解：P10940 舞动的夜晚

· · 题解

本题所需知识点

强联通分量

网络最大流

二分图的定义及匹配

二分图最大匹配及二分图匹配的必须边和可行边

完备匹配

#

题意简化

求二分图最大匹配的不可匹配边。 拓展：二分图的最大不可匹配边是对于任意一个匹配都没有的边。 #

题目求解

蓝书上讲得很清楚，就是属于同一个强连通分量，并且他在残量网络上不能没有边 一个二分图的最大匹配不是唯一的，若所有的最大匹配都含有的边，我们称其为必须边，对于任意一个最大匹配的边，我们称其为可行边。 最后我们一定要知道这条边再残量网络中属于不同的强联通分量即可 这里主要讲的是存储方法，一般来讲网络流是用链式前向星来写，但本人不是链式前向星党，所以我的代码是用动态数组写的。 具体就不展示了。 关于这题动态数组的做法基本没有对的做法，这里只提供一个修改做法，那就是二分。 但这这道题还能用歪式前向星。请见代码。 歪式前向星其实是链式前向星的变种，它就是用动态数组代替下一个和头指针。具体实现起来要比链式前向星慢一点，但实现较为简单。简单的把这条边加进去即可。 #

代码

歪式前向星

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,e;
vector<int>a[20005];
int tot=1;
int to[400005],id[400005];
void add(int u,int v,int w){
    tot++;
    a[u].push_back(tot);
    to[tot]=v;
    id[tot]=w;
    tot++;
    a[v].push_back(tot);
    to[tot]=u;
    id[tot]=0;
}
int d[20005];
int now[20005];
bool bfs(){
    memset(d,0,sizeof(d));
    queue<int>q;
    q.push(0);
    d[0]=1; 
    now[0]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<a[u].size();i++){
            int v=a[u][i];
            if(id[v]==0) continue;
            if(d[to[v]]) continue;
            d[to[v]]=d[u]+1;
            now[to[v]]=0;
            q.push(to[v]);
            if(to[v]==n+m+1) return 1;
        }
    }
    return 0;
}
int dfs(int u,int flow){
    if(u==n+m+1) return flow;
    int rest=flow;
    for(int i=now[u];i<a[u].size()&&rest;i++){
        now[u]=i;
        int v=a[u][i];
        if(id[v]==0) continue;
        if(d[to[v]]!=d[u]+1) continue;
        int k=dfs(to[v],min(rest,id[v]));
        if(k==0) d[to[v]]=0;
        id[v]-=k;
        id[v^1]+=k;
        rest-=k;
    }
    return flow-rest;
}
int dfn[20005],low[20005],times=0;
stack<int>st;
bool h[20005];
int belong[20005],cnt;
void tarjan(int u){
    dfn[u]=low[u]=++times;
    st.push(u);
    h[u]=1;
    for(int i=0;i<a[u].size();i++){
        int v=a[u][i];
        if(id[v]==0) continue;
        v=to[v];
        if(dfn[v]==0){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(h[v]) low[u]=min(low[u],dfn[v]); 
    }
    if(dfn[u]==low[u]){
        cnt++;
        while(st.top()!=u){
            h[st.top()]=0;
            belong[st.top()]=cnt;
            st.pop();
        }
        h[st.top()]=0;
        belong[st.top()]=cnt;
        st.pop();
    }
}
struct node{
    int u,v,e;
}ac[400005];
main(){
    cin>>n>>m>>e;
    for(int i=1;i<=n;i++) add(0,i,1);
    for(int i=1;i<=m;i++) add(i+n,n+m+1,1);
    for(int i=1;i<=e;i++){
        int u,v;
        cin>>u>>v;
        add(u,v+n,1);
       ac[i]={u,v,tot-1};
    }
    while(bfs()){
        while(dfs(0,LLONG_MAX));
    }
    for(int i=0;i<=n+m+1;i++){
        if(!dfn[i]) tarjan(i);
    }
    vector<int>ans;
    for(int i=1;i<=e;i++){
        int u=ac[i].u,v=ac[i].v,e=ac[i].e;
        if(id[e]&&belong[u]!=belong[v+n]) ans.push_back(i);
    }
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++) cout<<ans[i]<<" ";
    cout<<"\n"<<endl;
    return 0;
}

#

收尾与后期

这是蒟蒻的第二篇题解，蒟蒻也只是个三年级的小学生，请审核员大人手下留情，后续会持续更新。