题解 | #插座#

链接： https://ac.nowcoder.com/acm/problem/236773
思路：
首先针对每一个插座跑一遍匈牙利算法。
之后针对每一个插座，扩展两个点，其与其他电器的连接方式完全复制这个插座。
这样就可以模拟这个插排插在这个插座上的情况。
注意： 用邻接矩阵会超时。
代码：

#include<iostream>
#include<cstring>
#include<bitset>
using namespace std;
const int N=1510,M=75510;
int n,m,k;
bitset<N>st;
int match[N];
int match_[N];
int h[N], e[M], ne[M], idx=0; 
void add(int a, int b)
{
    e[idx] = b,ne[idx] = h[a], h[a] = idx++;
}
inline int read() {
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
bool find(int x,int match[])
{
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(st[j])
        {
            continue;
        }
        st[j]=true;
        if(match[j]==-1||find(match[j],match))
        {
            match[j]=x;
            return true;
        }
    }
    return false;
}
int main()
{
    memset(h,-1,sizeof h);
    memset(match,-1,sizeof match);
    cin>>n>>m>>k;
    for(int i=0;i<k;i++)
    {
        int a,b;
        a=read();
        b=read();
        add(a,b);
    }
    int res=0;
    for(int i=1;i<=n;i++)
    {
        st.reset();
        if(find(i,match))
        {
            res++;
        }
    }
    int Add=-1;
    int Idx=idx;
    for(int i=1;i<=n;i++)
    {
        int a=0;
        memcpy(match_,match,sizeof match);
        h[n+1]=-1;
        h[n+2]=-1;
        idx=Idx;
        for(int k=h[i];k!=-1;k=ne[k])
        {
            int j=e[k];
            add(n+1,j);
        }
        st.reset();
        if(find(n+1,match_))
        {
            a++;
        }
        for(int k=h[i];k!=-1;k=ne[k])
        {
            int j=e[k];
            add(n+2,j);
        }
        st.reset();
        if(find(n+2,match_))
        {
            a++;
        }
        Add=max(a,Add);
    }
    cout<<Add+res<<endl;
}