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

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) (1iMG) 连接顶点 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) (1iMH) 连接顶点 a i a_i ai b i b_i bi

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

  • 选择一对满足 1 ≤ i < j ≤ N 1\leq i \lt j\leq N 1i<jN 的整数 ( 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;
}

完结撒花~


http://www.kler.cn/a/306509.html

相关文章:

  • Postman上传图片如何处理
  • 某app最新版 vmp算法分析一
  • 蓝桥杯每日真题 - 第7天
  • Objection
  • 【STM32】基于SPI协议读写SD,详解!
  • 【设计模式】关联关系与依赖关系
  • Java 类和对象-小结(重要)
  • 基于STM32设计的智能货架(华为云IOT)(225)
  • VUE
  • 跨平台集成:在 AI、微服务和 Azure 云之间实现无缝工作流
  • 深入理解算法效率:时间复杂度与空间复杂度
  • Spark_natural_join
  • 828华为云征文 | 华为云Flexusx与Docker技术融合,打造个性化WizNote服务
  • 深入理解中比较两个字符串差异的方法”或“高效比对字符串:diff-match-patch:c++实战指南
  • c++面向对象
  • 栈OJ题——用栈实现队列
  • 嵌入式初学-C语言-数据结构--七
  • 【linux基础】linux中的开发工具(4)--调试器gdb的使用
  • 问题及解决方案汇总
  • 结构体内存对齐
  • 【算法】动态规划—最长公共子序列
  • HTML+CSS - 网页布局之多列布局定位
  • 网络安全应急响应概述
  • 用STM32做一个USB-TTL工具吧
  • JavaScript Promise 异步编程的一些代码分享
  • 远程桌面内网穿透是什么?有什么作用?