题目大意
有两个简单无向图,你每一次可以给第二个图添上或去掉一条边,有相应花费,问将两个图变为同构最少需要花费多少钱。
思路
观察数据范围,可以发现 N N N 非常小,可以考虑枚举全排列。所以我们就暴力枚举 1 1 1 到 N N N,把这个当前排列记在一个数组里, t [ i ] t[i] t[i] 表示在第一个图中点 i i i 对应第二个图中点 t [ i ] t[i] t[i], q [ i ] q[i] q[i] 表示在第二个图中点 i i i 对应第一个图中点 q [ i ] q[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;
}
标签:20,int,题解,Make,Isomorphic,40,cin,第二个,图中
From: https://blog.csdn.net/ArmeriaLeap/article/details/142283835