C - Make Isomorphic题解
C - Make Isomorphic
题目描述
给你简单的无向图 G G G 和 H H H ,每个图都有 N N N 个顶点:顶点 1 1 1 , 2 2 2 , … \ldots … , N N N 。图 G G G 有 M G M_G MG 条边,它的 i i i -th 边 ( 1 ≤ i ≤ M G ) (1\leq i\leq M_G) (1≤i≤MG) 连接顶点 u i u_i ui 和 v i v_i vi 。图 H H H 有 M H M_H MH 条边,它的 i i i -th 边 ( 1 ≤ i ≤ M H ) (1\leq i\leq M_H) (1≤i≤MH) 连接顶点 a i a_i ai 和 b i b_i bi 。
您可以在图 H H H 上执行以下操作,次数不限,可能为零。
- 选择一对满足 1 ≤ i < j ≤ N 1\leq i \lt j\leq N 1≤i<j≤N 的整数 ( i , j ) (i,j) (i,j) 。支付 A i , j A_{i,j} Ai,j 日元,如果 H H H 中的顶点 i i i 和 j j j 之间没有边,则添加一条边;如果有,则删除一条边。
求使 G G G 和 H H H 同构所需的最小总成本。
题目大意
题目要求我们找到使两个给定的无向图 G G G 和 H H H 同构所需的最小成本。我们可以通过改变 H H H 中的边来达到这一点,每次改变的成本由 A i , j A_{i,j} Ai,j 决定。
解决思路
A T f i r s t AT \ first AT first,我们需要读取输入:读取两个图的边信息及每对顶点间改变边的**『成本』**。
然后,初始化图:使用二维数组cost[][]
表示图
G
G
G和
H
H
H的邻接矩阵。
然后的然后全排列遍历:尝试所有的 N ! N! N! 种顶点排列组合,检查每种排列下 G G G和 H H H是否同构。
接着我们来计算成本:对于每种排列组合,计算以改变 H H H以匹配 G G G所需的**『成本』**。
『答案』的『记录』ans
记录最小值:记录所有可能排列下的最小成本。
咳,家人们3,2,1上代码
#include <iostream> // 基本输入输出流
#include <algorithm> // 通用算法(排序、查找、去重、二分查找等)
#include <vector> // 动态数组(空间不够会自动扩容)
#include <queue> // 队列(先进先出)
#include <stack> // 栈(先进后出)
#include <set> // 集合(有序不重复)
#include <map> // 键值对容器(映射)
#include <list> // 双向链表
#include <math.h> // 数学函数
#include <functional> // 通用的函数绑定和调用机制
#include <climits>
#include <bitset>
#define endl '\n'
#define pii pair<int, int>
#define pdd pair<double, double>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define int long long
using namespace std;
const int inf = 1e9 + 7;
const int mod = 998244353;
const int N = 2e5 + 10, M = N << 1;
int n,cost[10][10],p[10];
bool g[10][10],h[10][10];
void solve() {
cin >> n;
int mg;
cin >> mg;
for(int i = 1; i <= mg; ++i) {
int u, v;
cin >> u >> v;
g[u][v] = g[v][u] = true;
}
int mh;
cin >> mh;
for(int i = 1; i <= mh; ++i) {
int u, v;
cin >> u >> v;
h[u][v] = h[v][u] = true;
}
for(int i = 1; i < n; ++i) {
for(int j = i + 1; j <= n; ++j) {
cin >> cost[i][j];
cost[j][i] = cost[i][j];
}
}
for(int i = 1; i <= n; ++i) p[i] = i;
int ans = INT_MAX;
do {
int res = 0;
for(int i = 1; i <= n; ++i)
for(int j = i + 1; j <= n; ++j)
if(g[i][j] ^ h[p[i]][p[j]])
res += cost[p[i]][p[j]];
ans = min(ans, res);
} while(next_permutation(p + 1, p + n + 1));
cout << ans << endl;
}
signed main() {
//重定向输入输出
// freopen("pow.in", "r", stdin);
// freopen("pow.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int _ = 1;
// cin >> _; // 非多组测试数据请注释该行
while(_--) solve();
return 0;
}
完结撒花~