本文共 1784 字，大约阅读时间需要 5 分钟。

非常奈斯的一题

中心点非常特殊,而$n$不大,考虑枚举中心点

那么去掉中心点后,每个点还需要一个出度和一个入度

而对于原图中的边自然是保留越多越好,这样删掉的边就少,加上的边就多

发现什么了??最大匹配!!!

这样一来,令最大匹配为$temp$,图中的边有$bian$条,点数为$n-1$

这部分花费$(n-1-temp)+(biao-temp)$

再加上中心点需要补上去的边就好了

#include 
   
    using namespace std;const int maxn=2e5+10;const int inf=1e9;struct edge{
   	int to,nxt,flow;}d[maxn]; int head[maxn],cnt=1;int l[maxn],r[maxn],ok[maxn],vis[maxn],n,m,s,t;int dis[maxn],gap[maxn];void add(int u,int v,int flow){
   	d[++cnt]=(edge){
   v,head[u],flow},head[u]=cnt;	d[++cnt]=(edge){
   u,head[v],0},head[v]=cnt;}void bfs(){
   	for(int i=0;i<=t;i++)	dis[i]=-1,gap[i]=0;	gap[0]=1,dis[t]=0;	queue
    
     q; q.push(t);	while( !q.empty() )	{
   		int u=q.front(); q.pop();		for(int i=head[u];i;i=d[i].nxt )		{
   			int v=d[i].to;			if( dis[v]==-1 )			{
   				dis[v]=dis[u]+1;				gap[dis[v]]++;				q.push(v);			}		}	}}int ISAP(int u,int flow){
   	if( u==t )	return flow;	int res=flow;	for(int i=head[u];i;i=d[i].nxt )	{
   		int v=d[i].to;		if( dis[v]+1==dis[u]&&d[i].flow )		{
   			int temp = ISAP(v,min(d[i].flow,res));			res-=temp;			d[i].flow-=temp,d[i^1].flow+=temp;			if( res==0 )	return flow;		}	}	if( --gap[dis[u]]==0 )	dis[s]=t+1;	gap[++dis[u]]++;	return flow-res;}int main(){
   	cin >> n >> m;	s=0,t=n+n+1;	for(int i=1;i<=m;i++)	{
   		cin >> l[i] >> r[i];		if( l[i]==r[i] )	vis[l[i]]=1;		else	ok[l[i]]++,ok[r[i]]++;//统计每个点的出点和入点 	}	int res=1e9;	for(int i=1;i<=n;i++)	{
   		//枚举第i个点作为中心点 		int ans=2*(n-1)-ok[i],bian=0;		if( !vis[i] )	ans++;//需要有自环		for(int j=1;j<=m;j++)		{
   			if( l[j]==i||r[j]==i )	continue;			add(l[j],r[j]+n,1);				bian++;		}		for(int j=1;j<=n;j++) 			if( i!=j )	add(s,j,1),add(j+n,t,1);		bfs();		int temp=0;		while( dis[s]
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/109392633 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！