题解：AT_abc371_c [ABC371C] Make Isomorphic

题目大意

有两个简单无向图，你每一次可以给第二个图添上或去掉一条边，有相应花费，问将两个图变为同构最少需要花费多少钱。

思路

观察数据范围，可以发现 $N$ 非常小，可以考虑枚举全排列。所以我们就暴力枚举 $1$ 到 $N$，把这个当前排列记在一个数组里，$t[i]$ 表示在第一个图中点 $i$ 对应第二个图中点 $t[i]$，$q[i]$ 表示在第二个图中点 $i$ 对应第一个图中点 $q[i]$。然后，我们看第一个图中的边如果第二个图中没有就加上建边所需要的钱，第二个图中的边如果第一个图中没有就加上删边的钱，算出当前排列的答案。最后，我们把所有排列中计算的答案的最小值输出即可。

核心代码

for (int i = 1; i <= n; i++)
	t[i] = i, q[i] = i; // t和q含义见思路部分
do
{
	LL sum = 0;
	for (int i = 1; i <= n; i++)
		q[t[i]] = i; // 计算q
	for (int i = 1; i <= m1; i++)
		if (!h[t[x[i]]][t[y[i]]])
			sum += a[t[x[i]]][t[y[i]]]; // 建一条边
	for (int i = 1; i <= m2; i++)
		if (!g[q[u[i]]][q[v[i]]])
			sum += a[u[i]][v[i]]; // 删一条边
	ans = min(ans, sum);
} while (next_permutation(t + 1, t + n + 1)); // 全排列

完整代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;

int n, m1, m2;
int g[20][20]; // 第一个图（邻接矩阵）
int h[20][20]; // 第二个图（邻接矩阵）
int a[20][20]; // 含义见输入
int x[40], y[40]; // 第一个图中的边
int u[40], v[40]; // 第二个图中的边
int t[20], q[40]; // t和q，含义见思路
LL ans = 9e18; // 答案

int main()
{
	cin >> n >> m1;
	for (int i = 1; i <= m1; i++)
	{
		cin >> x[i] >> y[i];
		g[x[i]][y[i]] = 1; // 无向图
		g[y[i]][x[i]] = 1;
	}
	cin >> m2;
	for (int i = 1; i <= m2; i++)
	{
		cin >> u[i] >> v[i];
		h[u[i]][v[i]] = 1; // 无向图
		h[v[i]][u[i]] = 1;
	}
	for (int i = 1; i < n; i++)
		for (int j = i + 1; j <= n; j++)
		{
			cin >> a[i][j];
			a[j][i] = a[i][j]; // 对称
		}
	for (int i = 1; i <= n; i++)
		t[i] = i, q[i] = i;
	do
	{
		LL sum = 0;
		for (int i = 1; i <= n; i++)
			q[t[i]] = i;
		for (int i = 1; i <= m1; i++)
			if (!h[t[x[i]]][t[y[i]]])
				sum += a[t[x[i]]][t[y[i]]]; // 建边
		for (int i = 1; i <= m2; i++)
			if (!g[q[u[i]]][q[v[i]]])
				sum += a[u[i]][v[i]]; // 删边
		ans = min(ans, sum);
	} while (next_permutation(t + 1, t + n + 1)); // 全排列
	cout << ans << endl;
	return 0;
}