题解 CF387D 【George and Interesting Graph】
唔姆
一道十分因缺思厅的题
- 首先，看数据范围这么小，想都不用想，直接暴力枚举中心点（滑稽）
- 然后，对于每个中心点，我们都要记录下有多少个点连向它（记为into），它又连向多少个个别的点（记为out）。因为题目说了莫得重边，所以就直接统计边的个数好了。（有一点需要注意，如果是自环的话，只能算一次）为了满足中心点的约束，对于每个中心点，我们都需要2*n-1-into-out操作。（为什么-1？因为中心点也要连向自己，but只需要一次操作就可以完成）
- 接着，在满足中心点的约束之后，剩下的点都只剩下一个入度和一个出度了。那么这些点无论如何都是处于一个环中（有可能是自环）。也就意味着，如果想要最少的改变次数，我们要在现有的边中，尽量找出符合条件的边。
- 既然每个点只能向别的点连一次，也只能被别人连一次，这不就是标准的二分图最大匹配鸭！每次枚举中心点重新建图就OK了（记得不要把连向中心点或者从中心点连出来的边给匹配了）
- 在求出二分图最大匹配p之后我们需要如下操作
- 把没被匹配的边删掉，需要m-into-out-p次操作
- 把要加的边加上，需要n-1-p次操作
- 综上所述,ans=2*n-1-into-out+m-into-out-p+n-1-p。在枚举中心点的时候保留最小的ans就好了。
放上我巨丑无比的代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define MAXN 11050
#define MAXM 150005
using namespace std;
int head[MAXN],nextt[MAXM*2],to[MAXM*2],w[MAXM*2];
int n,m,S,T;
int cnt=-1;
int deep[MAXN];
struct line{
int from;
int to;
}l[MAXM];
void link(int a,int b,int c){
cnt++;
w[cnt]=c;
nextt[cnt]=head[a];
to[cnt]=b;
head[a]=cnt;
cnt++;
w[cnt]=0;
nextt[cnt]=head[b];
to[cnt]=a;
head[b]=cnt;
}
bool bfs(){
memset(deep,0,sizeof(deep));
queue<int> q;
while(!q.empty())q.pop();
q.push(S);
deep[S]=1;
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=head[now];i!=-1;i=nextt[i]){
if (w[i]&&!deep[to[i]]){
deep[to[i]]=deep[now]+1;
q.push(to[i]);
}
}
}
if (deep[T])return 1;else return 0;
}
int dinic(int now,int last){
if (now==T||!last)return last;
int ret=0;
for(int i=head[now];i!=-1;i=nextt[i]){
if(deep[to[i]]-1==deep[now]&&w[i]){
int zgl=dinic(to[i],min(w[i],last-ret));
if (zgl){
w[i]-=zgl;
w[i^1]+=zgl;
ret+=zgl;
}
}
}
if (!ret)deep[now]=-1;
return ret;
}
int into[MAXN],out[MAXN];
int main(){
cin>>n>>m;
S=0;T=MAXN-1;
memset(into,0,sizeof(into));
int a,b;
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
l[i].from=a;l[i].to=b;
into[b]++;
out[a]++;
if (a==b)into[b]--;
}
int anss=MAXM;
for(int i=1;i<=n;i++){
memset(head,-1,sizeof(head));
cnt=-1;
int tmp=into[i]+out[i];
for(int j=1;j<=n;j++){
link(S,j,1);
link(j+500,T,1);
}
for(int j=1;j<=m;j++){
if (l[j].to==i||l[j].from==i)continue;
link(l[j].from,l[j].to+500,1);
}
int ans=0;
while(bfs())
ans+=dinic(S,9999999);
anss=min(anss,n-1-ans+m-ans+2*n-1-tmp*2);
}
cout<<anss<<endl;
return 0;
}