当前位置：首页 > article >正文

C - Make Isomorphic题解

article 2024/9/22 3:39:59

C - Make Isomorphic

题目描述

给你简单的无向图 $G$ 和 $H$ ，每个图都有 $N$ 个顶点：顶点 $1$ , $2$ , $\ldots$ , $N$ 。图 $G$ 有 $M_G$ 条边，它的 $i$ -th 边 $(1\leq i\leq M_G)$ 连接顶点 $u_i$ 和 $v_i$ 。图 $H$ 有 $M_H$ 条边，它的 $i$ -th 边 $(1\leq i\leq M_H)$ 连接顶点 $a_i$ 和 $b_i$ 。

您可以在图 $H$ 上执行以下操作，次数不限，可能为零。

选择一对满足 $1\leq i \lt j\leq N$ 的整数 $(i, j)$ 。支付 $A_{i,j}$ 日元，如果 $H$ 中的顶点 $i$ 和 $j$ 之间没有边，则添加一条边；如果有，则删除一条边。

求使 $G$ 和 $H$ 同构所需的最小总成本。

题目大意

题目要求我们找到使两个给定的无向图 $G$ 和 $H$ 同构所需的最小成本。我们可以通过改变 $H$ 中的边来达到这一点，每次改变的成本由 $A_{i,j}$ 决定。

解决思路

$\ first$ ,我们需要读取输入:读取两个图的边信息及每对顶点间改变边的**『成本』**。

然后，初始化图：使用二维数组cost[][]表示图 $G$ 和 $H$ 的邻接矩阵。

然后的然后全排列遍历：尝试所有的 $N!$ 种顶点排列组合，检查每种排列下 $G$ 和 $H$ 是否同构。

接着我们来计算成本：对于每种排列组合，计算以改变 $H$ 以匹配 $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;
}