【CF387D】George and Interesting Graph（二分图最大匹配）

题意：给定一张n点m边没有重边的有向图，定义一个有趣图为：存在一个中心点满足以下性质：

1、除了这个中心点之外其他的点都要满足存在两个出度和两个入度。

2、中心 u 需要对任意顶点 v（包括自己）有一条(u,v)的边和(v,u)的边，即他们都要互通。

现在可以删除和添加边，使得给出的原图满足以上情况。询问删除和添加的最小操作次数。

n<=500,m<=1000

思路：枚举中心u，将边分为不相同的三部分：

1.u的自环，记为cir=(0..1)

2.u的出边或入边，记为out与in

3.与u无关的边

存在以下性质：原图删去中心以及1,2类边后每个点的出度与入度都为1

相当于一个点裂成了一个出点与入点，对这些点与边跑二分图最大匹配

考虑答案也有三部分组成：

1.原图中无用的边，即m-in-out-cir-maxmatch

2.需要添加的与中心无关的边，即n-1-maxmatch

3.需要添加的与中心相关的边，即2*(n-1)-in-out+1-cir

三部分加起来即为所求

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef pair<int,int> PII;

 typedef vector<int> VI;

 #define fi first

 #define se second

 #define MP make_pair

 #define N   1100

 #define M   1100

 #define eps 1e-8

 #define pi  acos(-1)

 #define oo  1e9

 int head[N],vet[N],nxt[N],match[N],flag[N],x[N],y[N],n,m,tot;

 int add(int a,int b)

 {

     nxt[++tot]=head[a];

     vet[tot]=b;

     head[a]=tot;

 }

 int dfs(int u)

 {

     flag[u]=;

     int e=head[u];

     while(e)

     {

         int v=vet[e];

         if(!match[v]||!flag[match[v]]&&dfs(match[v]))

         {

             match[v]=u;

             return ;

         }

         e=nxt[e];

     }

     return ;

 }

 int calc(int mid)

 {

     int in=;

     int out=;

     int cir=;

     memset(head,,sizeof(head));

     tot=;

     for(int i=;i<=m;i++)

     {

         if(x[i]==mid&&y[i]==mid)

         {

             cir=;

             continue;

         }

         if(y[i]==mid){in++; continue;}

         if(x[i]==mid){out++; continue;}

         add(x[i],y[i]);

     }

     memset(match,,sizeof(match));

     int maxmatch=;

     for(int i=;i<=n;i++)

     {

         memset(flag,,sizeof(flag));

         if(dfs(i)) maxmatch++;

     }

     int del=m-in-out-cir-maxmatch; //无用，删

     int plus=n--maxmatch;    //无关中心，加

     int t=*(n-)-in-out+-cir; //中心相关

     return del+plus+t;

 }

 int main()

 {

     //freopen("cf387d.in","r",stdin);

     //freopen("cf387d.out","w",stdout);

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++) scanf("%d%d",&x[i],&y[i]);

     int ans=oo;

     for(int i=;i<=n;i++) ans=min(ans,calc(i));

     printf("%d\n",ans);

     return ;

 }

巴特西

【CF387D】George and Interesting Graph（二分图最大匹配）

最新文章

热门文章