久久建筑网论坛_济南网站建设与维护_新产品推广方案怎么写_关于进一步优化

C - Make Isomorphic

题目描述

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

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

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

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

题目大意

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

解决思路

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

然后，初始化图：使用二维数组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;
}

完结撒花~