首页 > 其他分享 >题解:AT_abc371_c [ABC371C] Make Isomorphic

题解:AT_abc371_c [ABC371C] Make Isomorphic

时间:2024-09-15 14:21:57浏览次数:13  
标签:20 int 题解 Make Isomorphic 40 cin 第二个 图中

题目大意

有两个简单无向图,你每一次可以给第二个图添上或去掉一条边,有相应花费,问将两个图变为同构最少需要花费多少钱。

思路

观察数据范围,可以发现 N N N 非常小,可以考虑枚举全排列。所以我们就暴力枚举 1 1 1 到 N N N,把这个当前排列记在一个数组里, t [ i ] t[i] t[i] 表示在第一个图中点 i i i 对应第二个图中点 t [ i ] t[i] t[i], q [ i ] q[i] q[i] 表示在第二个图中点 i i i 对应第一个图中点 q [ i ] q[i] q[i]。然后,我们看第一个图中的边如果第二个图中没有就加上建边所需要的钱,第二个图中的边如果第一个图中没有就加上删边的钱,算出当前排列的答案。最后,我们把所有排列中计算的答案的最小值输出即可。

核心代码

for (int i = 1; i <= n; i++)
	t[i] = i, q[i] = i; // t和q含义见思路部分
do
{
	LL sum = 0;
	for (int i = 1; i <= n; i++)
		q[t[i]] = i; // 计算q
	for (int i = 1; i <= m1; i++)
		if (!h[t[x[i]]][t[y[i]]])
			sum += a[t[x[i]]][t[y[i]]]; // 建一条边
	for (int i = 1; i <= m2; i++)
		if (!g[q[u[i]]][q[v[i]]])
			sum += a[u[i]][v[i]]; // 删一条边
	ans = min(ans, sum);
} while (next_permutation(t + 1, t + n + 1)); // 全排列

完整代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;

int n, m1, m2;
int g[20][20]; // 第一个图(邻接矩阵)
int h[20][20]; // 第二个图(邻接矩阵)
int a[20][20]; // 含义见输入
int x[40], y[40]; // 第一个图中的边
int u[40], v[40]; // 第二个图中的边
int t[20], q[40]; // t和q,含义见思路
LL ans = 9e18; // 答案

int main()
{
	cin >> n >> m1;
	for (int i = 1; i <= m1; i++)
	{
		cin >> x[i] >> y[i];
		g[x[i]][y[i]] = 1; // 无向图
		g[y[i]][x[i]] = 1;
	}
	cin >> m2;
	for (int i = 1; i <= m2; i++)
	{
		cin >> u[i] >> v[i];
		h[u[i]][v[i]] = 1; // 无向图
		h[v[i]][u[i]] = 1;
	}
	for (int i = 1; i < n; i++)
		for (int j = i + 1; j <= n; j++)
		{
			cin >> a[i][j];
			a[j][i] = a[i][j]; // 对称
		}
	for (int i = 1; i <= n; i++)
		t[i] = i, q[i] = i;
	do
	{
		LL sum = 0;
		for (int i = 1; i <= n; i++)
			q[t[i]] = i;
		for (int i = 1; i <= m1; i++)
			if (!h[t[x[i]]][t[y[i]]])
				sum += a[t[x[i]]][t[y[i]]]; // 建边
		for (int i = 1; i <= m2; i++)
			if (!g[q[u[i]]][q[v[i]]])
				sum += a[u[i]][v[i]]; // 删边
		ans = min(ans, sum);
	} while (next_permutation(t + 1, t + n + 1)); // 全排列
	cout << ans << endl;
	return 0;
} 

标签:20,int,题解,Make,Isomorphic,40,cin,第二个,图中
From: https://blog.csdn.net/ArmeriaLeap/article/details/142283835

相关文章

  • 「KDOI-06-S」题解
    T2树上异或题面分析树形DP题考虑一颗子树内部的某种割边方式,假设其被分为\(n\)个连通块,每个连通块的权值分别为\(a_1,a_2,\dots,a_n\),那么该子树在这种割边方式下对答案的贡献就为\(\prod_{i=1}^{n}a_i\)。因此就可以从叶子向根不断合并,求出每种割边状态的值,时......
  • CMake构建学习笔记16-使用VS进行CMake项目的开发D4
    目录*1.概论2.详论2.1创建工程2.2加载工程2.3配置文件:飞数机场2.4工程配置2.5调试执行3.项目案例4.总结1.概论在之前的系列博文中,我们学习了如何构建第三方的依赖库,也学习了如何去组建自己的CMake项目,尤其是学习了CMake的核心配置文件CMakeLists.txt如......
  • Premake自动部署OpenGL项目
        很多朋友们在构建项目的时候应该都使用过CMake,在github和gitee的很多项目上面都能看到关于CMake的脚本。不过笔者认为,这东西有时候实在是过于繁重了,特别是这个构建的项目足够大的时候。在这里笔者为大家介绍一款轻量轻量化的软件Premake,它可以很方便构建visuals......
  • 【洛谷 P1596】[USACO10OCT] Lake Counting S 题解(深度优先搜索)
    [USACO10OCT]LakeCountingS题面翻译由于近期的降雨,雨水汇集在农民约翰的田地不同的地方。我们用一个的网格图表示。每个网格中有水(W)或是旱地(.)。一个网格与其周围的八个网格相连,而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图,......
  • Codeforces Round 972 (Div. 2) 2005C. Lazy Narek 题解
    原题链接:https://codeforces.com/contest/2005/problem/C看了教程发现都是用dp做的,在这里分享一个差不多的SPFA的思路(赛场上忘了Dijkstra不能有负边所以炸了)时间复杂度与dp同样是O(nm)形式化题意和翻译:有n个长度为m的字符串,你可以选择或不选择来拼接它们,但是不能更改字符串的......
  • 食物链题解
    双倍经验:P2024[NOI2001]食物链当问题要求维护一些对立的关系时(朋友、敌人),就可以用种类并查集实现。因为有三种关系所以并查集的数组要开三倍空间,第一倍空间存同类关系,第二倍存捕食关系,第三倍存被捕食关系。注意:一的猎物的猎物就是一的天敌,其他就可以直接并查集维护即可。注......
  • [ABC371D] 1D Country 题解
    这题,怎么说呢,\(STL\)大法好。前置芝士:lower_pound函数在结构体上的使用。那其实这题便是一个二分前缀和的水题了。结构体存储每个村庄的距离\(x\),人口\(d\)。对于每个输入的\([l,r]\)二分查找其对应的村庄,进行一次答案的统计,输出即可。代码:#include<bits/stdc++.......
  • 【LGR-200-Div.4】洛谷入门赛 #27 A-H题解
    A#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;mt19937rnd(time(0));#defineintlonglongtypedeftuple<int,int,int>tp;#definexfirst#defineysecondtypedefpair<int,int>pii;typedefpair<double,double>......
  • 题解 [ABC371G] Lexicographically Smallest Permutation(中文/English)
    本题解提供英文版,位于示例代码之后。Englishversionofthiseditorialisprovidedafterthesamplecode.官方题解竟然用Python来算高精度lcm,我来提供一个可以避免一切大整数运算的方法。考察\(u\getsP_u\)这张图的每个置换环。为了使答案字典序最小,显然需要从前往后......
  • CMake构建学习笔记16-使用VS进行CMake项目的开发
    目录1.概论2.详论2.1创建工程2.2加载工程2.3配置文件2.4工程配置2.5调试执行3.项目案例4.总结1.概论在之前的系列博文中,我们学习了如何构建第三方的依赖库,也学习了如何去组建自己的CMake项目,尤其是学习了CMake的核心配置文件CMakeLists.txt如何编写。长期以来,CMakeLis......