[atcoder abc 371c]Make Isomorphic

题目链接

建议在洛谷上阅读。

首先，我们要读懂图同构的意思。

简单来说，图同构的意思是将所有点重新排列，所得到的图与原图图同构。

---

由于 $N\le 8$，所以可以直接全排列顶点，求出每次花费，最后输出最小值即可。

图同构的边一定没有变化，所以求花费时，只要两个图的某条边不同，就加上花费。

全排列可以直接使用 next_permutation 就行了，也可以写 dfs。

---

#include<bits/stdc++.h>
using namespace std;
int n, m1, m2;
//用邻接矩阵存图
int a[10][10] = {0};
int b[10][10] = {0};
int w[10][10] = {0};
int p[10];
int main(){scanf("%d %d", &n, &m1);for(int i = 1; i <= m1; ++ i){int x, y;输入 x 和 ya[x][y] = a[y][x] = 1;}scanf("%d", &m2);for(int i = 1; i <= m2; ++ i){int x, y;输入 x 和 yb[x][y] = b[y][x] = 1;}for(int i = 1; i <= n; ++ i){for(int j = i + 1; j <= n; ++ j){scanf("%d", &w[i][j]);w[j][i] = w[i][j];}}//初始化for(int i = 1; i <= n; ++ i){p[i] = i;}long long ans = 1e17;do{//计算费用long long sum = 0;for(int i = 1; i <= n; ++ i){for(int j = i + 1; j <= n; ++ j){if(a[i][j] != b[p[i]][p[j]]){sum += w[p[i]][p[j]];}}}ans = min(ans, sum);}while(next_permutation(p + 1, p + n + 1));printf("%lld", ans);return 0;
}