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

[ SNOI 2013 ] Quare

Description

题目链接

求一张无向带权图的边双连通生成子图的最小代价。

Solution

核心的思路是,一个点双连通分量肯定是一堆环的并。

考虑增量地构造这个边双连通图,每次把一个环并进去,相当于加入了一条链。

那么这个转移需要:原集合的代价,链的代价,链的端点连入集合的代价。

\(A\) 为新图点集,\(S\) 为原图点集,设 \(f[S]\) 表示点集 \(S\) 构成边双连通分量的最小代价。

\(T\) 为新加入链的点集,\(u,v\) 分别为加入的链的端点,设 \(g[u][v][T]\) 表示该链的最小代价。

\(mm[u][S]\) 表示点 \(u\) 向集合 \(S\) 中的点所连边中,边权最小值。
\[ f[A]=f[S]+g[u][v][T]+mn[u][S]+mn[v][S] \]
但是注意,如果新加入的链退化成了一个点,加入的代价就算少了。

因此设 \(sec[u][S]\) 表示点 \(u\) 向集合 \(S\) 中的点所连边中,边权次小值。

那么对于 \(u=v\) 的情况:
\[ f[A]=f[S]+g[u][u][T]+mn[u][S]+sec[u][S] \]
预处理 \(mn\)\(sec\) 复杂度 \(\mathcal O(n^2\times 2^n)\)

预处理 \(g\) 暴力枚举一个端点的变化,复杂度 \(\mathcal O(n^3\times 2^n)\)

计算 \(f\) 需要枚举子集,然后枚举 \(u, v\) ,复杂度 \(\mathcal O(n^2\times 3^n )\)

#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 15
#define M 105
#define S 4105
using namespace std;
 
inline int rd() {
  int x = 0;
  char c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) {
    x = x * 10 + (c ^ 48); c = getchar();
  }
  return x;
}
 
int n, m, tot, lim, hd[N];
 
struct edge{int w, to, nxt;} e[M << 1];
 
inline void add(int u, int v, int w) {
  e[++tot].to = v; e[tot].w = w;
  e[tot].nxt = hd[u]; hd[u] = tot;
}
 
//mn[i][S]: i 到 S 最短路
//sec[i][S]: i 到 S 次短路
//g[i][j][S]: 一条链,节点集合为 S, 端点分别为 i, j
//f[S]: 集合为 S 的合法方案
 
int f[S], g[N][N][S], mn[N][S], sec[N][S];
 
inline void mmin(int &x, int y) {x = min(x, y);}
 
inline int countbit(int s) {
  int res = 0;
  for (int i = 0; i < n; ++i)
    res += ((s & (1 << i)) > 0);
  return res;
}
 
inline void work() {
  n = rd(); m = rd();
  tot = 0; lim = (1 << n);
  for (int i = 0; i <= n; ++i) hd[i] = 0;
  for (int i = 1, u, v, w; i <= m; ++i) {
    u = rd() - 1; v = rd() - 1; w = rd();
    add(u, v, w); add(v, u, w);
  }
  memset(f, 0x1f, sizeof(f));
  memset(g, 0x1f, sizeof(g));
  memset(mn, 0x1f, sizeof(mn));
  memset(sec, 0x1f, sizeof(sec));
  int inf = f[0];
  //处理 mn 和 sec
  for (int s = 1; s < lim; ++s)
    for (int u = 0; u < n; ++u)
      if ((s & (1 << u)) == 0)
        for (int i = hd[u], v; i; i = e[i].nxt) {
          v = e[i].to;
          if ((s & (1 << v)) == 0) continue;
          if (e[i].w < mn[u][s]) {
            sec[u][s] = mn[u][s];
            mn[u][s] = e[i].w; continue;
          } else sec[u][s] = min(sec[u][s], e[i].w);
        }
  //处理 g
  for (int u = 0; u < n; ++u) g[u][u][1 << u] = 0;
  for (int s = 1; s < lim; ++s)
    for (int u = 0; u < n; ++u)
      for (int x = 0; x < n; ++x)
        if (g[u][x][s] < inf)
          for (int i = hd[u], v; i; i = e[i].nxt) {
            v = e[i].to;
            if (s & (1 << v)) continue;
            mmin(g[v][x][s | (1 << v)], g[u][x][s] + e[i].w);
          }
  //处理 f
  for (int u = 0; u < n; ++u) f[1 << u] = 0;
  for (int nw = 1; nw < lim; ++nw)
    if (countbit(nw) >= 2) {
      for (int s = nw & (nw - 1); s; s = (s - 1) & nw) {
        int t = nw - s;
        for (int u = 0; u < n; ++u)
          if (s & (1 << u)) for (int v = 0; v < n; ++v)
            if (s & (1 << v) && g[u][v][s] < inf) {
              if (u == v) f[nw] = min(f[nw], f[t] + g[u][v][s] + mn[u][t] + sec[u][t]);
              else f[nw] = min(f[nw], f[t] + g[u][v][s] + mn[u][t] + mn[v][t]);
            }
      }
    }
    if (f[lim - 1] == inf) puts("impossible");
    else printf("%d\n", f[lim - 1]);
}
 
int main() {
  int testcase = rd();
  while (testcase--) work();
  return 0;
}

转载于:https://www.cnblogs.com/SGCollin/p/10620216.html

相关文章:

  • 打开文件夹
  • Spring Boot Service注入为null mapper注入为null @Component注解下@Value获取不到值 WebsocketServer类里无法注入service...
  • day27T2改错记
  • 《深度学习入门基于Python的理论与实现》PDF及代码+《21个项目玩转深度学习》PDF及代码+原理到实践总结...
  • 一些常用的正则表达式示例
  • C++学习(三十四)(C语言部分)之 链表
  • RIpng配置(GNS3)(第九组)
  • halcon预处理函数
  • [博弈论]
  • 一个正在读本科的计院学生
  • 排序算法之快速排序QuickSort
  • CSS中一个冒号和两个冒号有什么区别
  • MSF内网渗透 扫描模块
  • [转帖]安德斯·海尔斯伯格
  • [转帖]Linux分页机制之概述--Linux内存管理(六)
  • 【知识碎片】第三方登录弹窗效果
  • JavaSE小实践1:Java爬取斗图网站的所有表情包
  • Java知识点总结(JDBC-连接步骤及CRUD)
  • PAT A1120
  • Python十分钟制作属于你自己的个性logo
  • Redis中的lru算法实现
  • storm drpc实例
  • WordPress 获取当前文章下的所有附件/获取指定ID文章的附件(图片、文件、视频)...
  • 基于web的全景—— Pannellum小试
  • 技术发展面试
  • 前端
  • 微信支付JSAPI,实测!终极方案
  • 我与Jetbrains的这些年
  • 异常机制详解
  • 鱼骨图 - 如何绘制?
  • 再次简单明了总结flex布局,一看就懂...
  • 追踪解析 FutureTask 源码
  • kubernetes资源对象--ingress
  • zabbix3.2监控linux磁盘IO
  • 专访Pony.ai 楼天城:自动驾驶已经走过了“从0到1”,“规模”是行业的分水岭| 自动驾驶这十年 ...
  • ​LeetCode解法汇总2182. 构造限制重复的字符串
  • ###项目技术发展史
  • #HarmonyOS:软件安装window和mac预览Hello World
  • #中的引用型是什么意识_Java中四种引用有什么区别以及应用场景
  • (3)选择元素——(14)接触DOM元素(Accessing DOM elements)
  • (MATLAB)第五章-矩阵运算
  • (保姆级教程)Mysql中索引、触发器、存储过程、存储函数的概念、作用,以及如何使用索引、存储过程,代码操作演示
  • (附源码)计算机毕业设计ssm电影分享网站
  • (力扣题库)跳跃游戏II(c++)
  • (十八)三元表达式和列表解析
  • (数位dp) 算法竞赛入门到进阶 书本题集
  • (一)spring cloud微服务分布式云架构 - Spring Cloud简介
  • (转)JAVA中的堆栈
  • (转)mysql使用Navicat 导出和导入数据库
  • (转)母版页和相对路径
  • (转)微软牛津计划介绍——屌爆了的自然数据处理解决方案(人脸/语音识别,计算机视觉与语言理解)...
  • (转载)利用webkit抓取动态网页和链接
  • *2 echo、printf、mkdir命令的应用
  • .mysql secret在哪_MYSQL基本操作(上)
  • .NET Framework 和 .NET Core 在默认情况下垃圾回收(GC)机制的不同(局部变量部分)