题解 | #中心图#

枚举每一个点
针对第二个条件，缺哪些边，添哪些边就可以了
针对第三个条件，用最小路径点覆盖就可以了

#include<iostream>
#include<cstring>
using namespace std;
int n,m;
const int N=1e3;
int g[N][N];
int st[N];
int match[N];
int find(int u,int x)
{
    for(int i=1;i<=n;i++)
    {
        if(i==x)
        {
            continue;
        }
        if(st[i])
        {
            continue;
        }
        if(!g[u][i])
        {
            continue;
        }
        st[i]=true;
        if(match[i] == -1 || find(match[i],x))
        {
            match[i]=u;
            return true;
        }
    }
    return false;
}
int solve(int x)
{
    memset(match,-1,sizeof match);
    int sum=0; // 满足条件2需要满足加的边 已存在的边就是 2 * (n - 1) + 1 - sum
    for(int i=1;i<=n;i++)
    {
        if(!g[x][i])
        {
            sum++;
        }
        if(i==x)
        {
            continue;
        }
        if(!g[i][x])
        {
            sum++;
        }
    }
    int res=0; // 除去与u相关的边后，有用的边的数量
    for(int i=1;i<=n;i++)
    {
        if(i==x)
        {
            continue;
        }
        memset(st,false,sizeof st);
        if(find(i,x))
        {
            res++; 
        }
    }
    int shan= m - (2 * (n - 1) + 1 - sum) - res;// 除去与u相关的边后，无用的边的数量
    int jia=(n-1)-res;
    return shan+jia+sum;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        g[a][b]=true;
    }
    int res=0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        res=min(res,solve(i));
    }
    cout<<res;
}