中心图

NC236759. 中心图

描述

给出一个 $n$ 个节点， $m$ 条边的有向图，你可以进行若干次操作，每次操作可以删除图中的一条边或者添加一条有向边，使得原图变为中心图。

定义一个图是中心图，当且仅当它满足如下条件：

1. 图中没有重边。

2. 存在一个点 $u$ ，满足对于任意的 $v \in [1,n]$ ，图中都存在边 $(u,v)$ 和 $(v,u)$ ，我们称 $u$ 是中心点。注意：这意味着 $u$ 需要有自环。

3. 除了中心点之外，其它所有点的入度和出度均为2。

此外，你需要保证操作次数尽可能少。

输入描述

第一行输入两个整数  ，分别表示原图的点数和边数。
接下来行，每行输入两个整数  ，表示从  到  有一条有向边相连。保证输入不含重边。

输出描述

输出一行一个整数，表示让原图变为中心图需要的最小操作次数。

示例1

输入:

输出:

说明:

给出的图已经是一个中心图，中心点是3。

示例2

输入:

3 1
2 2

输出:

示例3

输入:

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 25ms, 内存消耗: 488K, 提交时间: 2023-05-02 23:09:49

#include<bits/stdc++.h>
#define N 1005
using namespace std;
vector<int> e[N];
int ins[N],out[N];
int c[N],vis[N],idx;
int n,m,ans=1e9;
bool dfs(int x){
    for(auto y:e[x]){
        if(vis[y]==idx) continue;
        vis[y]=idx;
        if(!c[y]||dfs(c[y])){
            c[y]=x;
            return 1;
        }
    }
    return 0;
}
void work(int x){
    memset(c,0,sizeof(c));
    int sum=0;
    for(int i=1;i<=n;i++){
        if(i==x) continue;
        vis[x]=1+idx++;
        sum+=dfs(i);
    }
    ans=min(ans,n*3+m-2-ins[x]*2-out[x]*2-sum*2);
}
int main(){
    cin>>n>>m;
    int u,v;
    for(int i=1;i<=m;i++){
    	cin>>u>>v;
        e[u].push_back(v);
        ++ins[v],++out[u];
        if(u==v) --ins[v];
    }
    for(int i=1;i<=n;i++) work(i);
    cout<<ans<<endl;
}