首页 算法

# 题意分析

操作最少的次数，构成有趣图，注意无重边，有向边。

  • 操作分为加边和删边。
  • 有趣图定义
    • 有一个中心，满足此点有自环，且与其他结点有双向边。
    • 除中心点外的结点，满足出度 = 入度 = 2。

# 算法分析

1、仔细分析有趣图的定义，发现如下性质：

  • 中心的边数为 (n−1)×2+1(n-1)\times 2+1，也就是它与其他结点要有双向边再加自己的一个自环，无重边所以构造中心点时不可能做删除操作，只能加边或不操作。
  • 其他结点的出入度为 2，排除掉与中心点连接的双向边，其点的度一定为一进一出。

2、如何判断结点的度满足一进一出。

图一，图二都是满足结点度一进一出。所以 nn 个结点需要 nn 条相连边（首尾）。

图三不满足，只有两条相连边 (e1,e2)(e_1,e_2) 或者选择 (e1,e3)(e_1,e_3) 即有用边，还需要添加 n−2n-2 边有用边，同时还要减掉 1 条边，即总边数减去有用边，也就是要删除的无用边。

方法 1：拆点，一个点拆为进点和出点，建立二分图。

​

左边的点求匹配，最大匹配就是有用的边。

方法 2：直接将图看成二分图，利用有向边每个点都求匹配。

3、枚举每个点做中心点。

  • 中心点 V，计算维护中心需要的边 (n−1)×2+1−∑(n-1)\times 2+1-\sum

  • 删除 V 点，也就是包含相应的边

  • 剩下的图，计算最大匹配，满足一进一出的边数需要的操作（添加边 + 删除边）。

#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <vector>
#include <iostream>
using namespace std;
const int N = 550, INF = INT_MAX;
vector<int> g[N];
int c, n, m;
int tag = 0, vis[N], match[N];
bool mp[N][N];
bool dfs(int u) {
	for(int i = 0; i < g[u].size(); ++i) {
		int v = g[u][i];
		if(v == c) continue;
		if(vis[v] == tag) continue;
		vis[v] = tag;
		if(match[v] == 0 or dfs(match[v])) {
			match[v] = u;
			return true;
		}
	}
	return false;
}
int best = INF;
int main() {
	
	scanf("%d%d", &n, &m);
	
	int sum0 = 0;
	for(int i=1, u, v; i<=m; ++i) {
		scanf("%d%d", &u, &v);
		g[u].push_back(v);
		mp[u][v] = true;
		++sum0;
	}
	
	for(int i=1; i<=n; ++i) {
		memset(match, 0, sizeof match);
		c = i;
		int ans = 0;
		int sum1 = 0;
		for(int j=1; j<=n; ++j) {
			if(j == c) {
				if(mp[c][c]) ++sum1;
				continue;
			}
			if(mp[j][c]) ++sum1;
			if(mp[c][j]) ++sum1;
		}
		ans += 2*(n-1) + 1 - sum1;
		//printf("ans1 = %d\n", ans);
		//printf("sum1 = %d\n", sum1);
		int sum2 = 0;
		for(int j=1; j<=n; ++j) {
			++tag;
			if(j == c) continue;
			if(dfs(j)) ++sum2;
		}
		
		ans += sum0 - sum1 - sum2 + n-1 - sum2;
		
		best = min(best, ans);
		//printf("ans2 = %d\n", ans);
		//printf("sum2 = %d\n", sum2);
	}
	
	printf("%d\n", best);
	return 0;
}
  
 更新于