IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 【PR #5 A】双向奔赴(状压DP) -> 正文阅读

[数据结构与算法]【PR #5 A】双向奔赴(状压DP)

双向奔赴

题目链接:PR #5 A

题目大意

给你一个简单无向图,然后你要给每条边定向,每个边每个方向有不一样的费用。
然后要你用最小的费用使得这张图强连通,如果无法强连通输出 -1。

思路

首先考虑最暴力的方法,可以直接找一条路径从 1 1 1 出发经过所有点(可以重复经过点),然后回到 1 1 1

然后我们简化一下题意,我们可以默认选边权小的那个,然后如果要选另一边就要加上差的费用,然后最后加上边权小和。

然后发现我们其实可以把它分割,分割成若干个环。
具体一点就是你已经有一个强连通的子集,然后你每次从一个子集里面的点往外走,一直走没有见过的,然后最后走回到子集里面,然后你外面见到的点也就也跟着强连通了。(这个一直不走见过的是没问题的,因为走见过的你可以把它拆成若干个没有见过的)
然后就有一个大概的状压想法了: g S g_S gS? 表示当前 S S S 这个子集强连通的最小费用, f S , i , j f_{S,i,j} fS,i,j? S S S 这个子集强连通,环的终点是 i i i,现在在 j j j
(然后为了我们能表示出走出环的点,所以 f S , i , j f_{S,i,j} fS,i,j? S S S 就表示成强连通的子集与现在要加上的点的并集)
然后就是三种,一个是从 g g g f f f,接着是 f f f 内部转移,最后 f f f g g g

复杂度为 O ( n 3 2 n ) O(n^32^n) O(n32n) 能过。

然后你会发现锅了,因为你这样是不能保证一条边只会从一个方向走的。
(就比如你从 g g g 走一个点到 f f f 结果你直接从 f f f 走回 g g g 了)
那我们考虑怎么办,因为这个时候复杂度已经是很大的了不能再乘 n n n,考虑压缩一下,会发现你 f S , i , j f_{S,i,j} fS,i,j? j j j 是一定在 S S S 中的,那我们能不能不在呢?
自然是可以的,那如果我们用不在的方式转移,但是一开始又在呢?
你会发现就不能直接归到答案里面(因为你答案枚举 j j j 是要不在 S S S 里面的),而是要通过走一步消除掉这个特异性(因为你无论怎样都是正常转移,那下一个点肯定不在点集里面),所以就可以走回去了。
然后就可以用这个很妙的方法特判掉这个情况啦!
(具体实现可以看代码)

代码

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

const int N = 18;
int n, a[N][N], f[1 << N][N][N], g[1 << N], ans;

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf("%d", &a[i][j]);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < i; j++)
			if (a[i][j] != -1) {
				int x = min(a[i][j], a[j][i]);
				a[i][j] -= x; a[j][i] -= x; ans += x;
			}
	
	memset(f, 0x7f, sizeof(f));
	memset(g, 0x7f, sizeof(g)); int inf = g[0];
	g[1] = 0;
	for (int S = 1; S < (1 << n); S++) {
		if (g[S] < inf) {
			for (int i = 0; i < n; i++) if ((S >> i) & 1)
				for (int s = 0; s < n; s++) if ((S >> s) & 1)
					for (int j = 0; j < n; j++) if (!((S >> j) & 1) && a[s][j] != -1) {
						if (s != i) f[S][i][j] = min(f[S][i][j], g[S] + a[s][j]);
							else f[S | (1 << j)][i][j] = min(f[S | (1 << j)][i][j], g[S] + a[s][j]);//不能从起点出发到这个点就直接到终点 
					}
		}
		for (int i = 0; i < n; i++) if ((S >> i) & 1)
			for (int j = 0; j < n; j++) if (f[S][i][j] < inf)
				for (int k = 0; k < n; k++) if (!((S >> k) & 1) && a[j][k] != -1)
					f[S | (1 << j)][i][k] = min(f[S | (1 << j)][i][k], f[S][i][j] + a[j][k]);
		for (int i = 0; i < n; i++) if ((S >> i) & 1)
			for (int j = 0; j < n; j++) if (!((S >> j) & 1) && f[S][i][j] < inf && a[j][i] != -1)
				g[S | (1 << j)] = min(g[S | (1 << j)], f[S][i][j] + a[j][i]);
	}
	
	if (g[(1 << n) - 1] < inf) ans += g[(1 << n) - 1];
		else ans = -1;
	printf("%d", ans);
	
	return 0;
} 
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-06-29 19:19:22  更:2022-06-29 19:23:23 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/29 18:36:55-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码