UVa1104/LA5131 Chips Challenge

2024-09-06 05:52
文章标签 challenge chips uva1104 la5131

本文主要是介绍UVa1104/LA5131 Chips Challenge,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

UVa1104/LA5131 Chips Challenge

  • 题目链接
  • 题意
  • 分析
  • AC 代码
    • 上下界循环费用流版本
    • 优化建图版本

题目链接

  本题是2011年icpc世界总决赛的D题

题意

  在一个N×N(N≤40)网格里放芯片。其中一些格子已经放了芯片(用C表示),有些格子不能放(用/表示),有些空格子可以放或者不放芯片(用.表示)。还要放一些芯片(用W表示),使得第i行的总芯片个数(C和W之后)等于第i列。为了保证散热,任意行/列的芯片(包括C和W)不能超过总芯片数的A/B。

分析

  先不考虑任意行/列的芯片不能超过总部件数的A/B,则是上下界循环费用流问题:将行 i i i看成结点 x i x_i xi,列 j j j看成结点 y j y_j yj,已经放了芯片的格子 ( i , j ) (i,j) (i,j)对应上下界均为1费用为0的有向边 i → j i\rightarrow j ij,可以放或者不放的格子 ( i , j ) (i,j) (i,j)对应容量为1费用为0的有向边 x i → y j x_i\rightarrow y_j xiyj y i y_i yi x i x_i xi连容量为 i n f inf inf费用为-1的有向边来满足第i行的总芯片个数等于第i列的约束。

  再来看任意行/列的芯片不能超过总部件数的A/B这一点怎么处理,如果枚举总芯片数(即枚举最大流),需要跑 O ( n 2 ) O(n^2) O(n2)次费用流,会超时。可以枚举每行/列的最大芯片总数 k k k(即 y i y_i yi x i x_i xi连容量为 k k k费用为-1的有向边)求出最大费用 c c c(即最大芯片总数):若 c × A < k × B c\times A<k\times B c×A<k×B则不满足任意行/列的芯片不能超过总部件数的A/B,否则更新答案。

  注意:上下界网络拆边调整后跑最大流,附加源点 s s s的出边都满流时才可行;循环流消除负权边,也是加源点 s s s的出边都满流时才可行。因此要检验最大流是否为源点 s s s流出的总容量。

  利用补集的思想,可以得到更优的建图方法:已经放了芯片的格子不连边;可以放或者不放的格子 ( i , j ) (i,j) (i,j)连容量为1费用为1的有向边 x i → y j x_i\rightarrow y_j xiyj(跑完费用流后此边若有流量则表示该格子不放芯片); x i x_i xi y i y_i yi连容量为 k k k费用为0的有向边来满足第i行的总芯片个数等于第i列的约束;源点 s s s x i x_i xi连容量为第 i i i行所有已经放了芯片的格子总数与可以放或者不放的格子总数之和费用为0的有向边; y i y_i yi向汇点 t t t连容量为第 i i i列所有已经放了芯片的格子总数与可以放或者不放的格子总数之和费用为0的有向边。跑最小费用最大流,得到不能放的芯片数最小值(即最大芯片数的)。

AC 代码

上下界循环费用流版本

#include <iostream>
#include <cstring>
using namespace std;#define M 3520
#define N 82
struct edge {int u, v, cap, flow, cost;} e[M];
int g[N][N], q[M*N], a[N], d[N], p[N], cnt[N], hu[N], c, n, h, b, kase = 0; bool vis[N]; void add_edge(int u, int v, int cap, int cc) {e[c] = {u, v, cap, 0, cc}; g[u][cnt[u]++] = c++; e[c] = {v, u, 0, 0, -cc}; g[v][cnt[v]++] = c++;
}int solve() {int s = 0, t = 2*n+1, f = 0, cc = 0;memset(cnt, c = 0, sizeof(cnt)); memset(a, 0, sizeof(a)); memset(d, 0, sizeof(d));for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j) {char x; cin >> x;if (x == 'C') ++a[j+n], ++a[i], ++f, ++d[i], --d[j];else if (x == '.') add_edge(i, j+n, 1, 0);}for (int i=1; i<=n; ++i) {hu[i] = c; add_edge(i, i+n, n, 1); add_edge(s, i, n, 0); add_edge(i+n, t, n, 0);if (a[i]) add_edge(i, t, a[i], 0);if (a[i+n]) add_edge(s, i+n, a[i+n], 0);if (d[i] || f*h < a[i]*b) cc = -1;}for (int k=n; k>0; --k) {for (int i=0; i<c; ++i) e[i].flow = 0;for (int i=1; i<=n; ++i) e[hu[i]].cap = e[hu[i]+2].cap = e[hu[i]+4].cap = k;int cost = n*k, flow = cost+f;while (true) {memset(d, 1, sizeof(d)); memset(vis, 0, sizeof(vis)); d[s] = 0; q[0] = s; a[s] = M;int head = 0, tail = 1;while (head < tail) {int u = q[head++]; vis[u] = false;for (int i=0; i<cnt[u]; ++i) {const edge& ee = e[g[u][i]];if (ee.cap > ee.flow && d[ee.v] > d[u]+ee.cost) {d[ee.v] = d[u]+ee.cost;p[ee.v] = g[u][i];a[ee.v] = min(a[u], ee.cap-ee.flow);if (!vis[ee.v]) vis[q[tail++] = ee.v] = true;}}}if (d[t] > M) break;flow -= a[t]; cost -= d[t] * a[t];for (int u=t; u!=s; u=e[p[u]].u) e[p[u]].flow += a[t], e[p[u]^1].flow -= a[t];}if (flow || cost*h < k*b) continue;cc = max(cc, cost-f);}return cc;
}int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);while (cin >> n >> h >> b && n) {int cc = solve();cout << "Case " << ++kase << ": ";cc < 0 ? cout << "impossible" << endl : cout << cc << endl;}return 0;
}

优化建图版本

#include <iostream>
#include <cstring>
using namespace std;#define M 3440
#define N 82
struct edge {int u, v, cap, flow, cost;} e[M];
int g[N][N], q[M*N], a[N], d[N], p[N], cnt[N], hu[N], c, n, h, b, kase = 0; bool vis[N]; void add_edge(int u, int v, int cap, int cc) {e[c] = {u, v, cap, 0, cc}; g[u][cnt[u]++] = c++; e[c] = {v, u, 0, 0, -cc}; g[v][cnt[v]++] = c++;
}int solve() {int s = 0, t = 2*n+1, f = 0, c0 = 0, cc = -1;memset(cnt, c = 0, sizeof(cnt)); memset(a, 0, sizeof(a));for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j) {char x; cin >> x;if (x == 'C') ++a[j+n], ++a[i], ++f, ++c0;else if (x == '.') ++a[j+n], ++a[i], ++f, add_edge(i, j+n, 1, 1);}for (int i=1; i<=n; ++i) {hu[i] = c; add_edge(i, i+n, n, 0);if (a[i]) add_edge(s, i, a[i], 0);if (a[i+n]) add_edge(i+n, t, a[i+n], 0);}for (int k=0; k<=n; ++k) {for (int i=0; i<c; ++i) e[i].flow = 0;for (int i=1; i<=n; ++i) e[hu[i]].cap = k;int flow = f, cost = f;while (true) {memset(d, 1, sizeof(d)); memset(vis, 0, sizeof(vis)); d[s] = 0; q[0] = s; a[s] = M;int head = 0, tail = 1;while (head < tail) {int u = q[head++]; vis[u] = false;for (int i=0; i<cnt[u]; ++i) {const edge& ee = e[g[u][i]];if (ee.cap > ee.flow && d[ee.v] > d[u]+ee.cost) {d[ee.v] = d[u]+ee.cost;p[ee.v] = g[u][i];a[ee.v] = min(a[u], ee.cap-ee.flow);if (!vis[ee.v]) vis[q[tail++] = ee.v] = true;}}}if (d[t] > M) break;flow -= a[t]; cost -= d[t] * a[t];for (int u=t; u!=s; u=e[p[u]].u) e[p[u]].flow += a[t], e[p[u]^1].flow -= a[t];}if (flow || cost*h < k*b) continue;cc = max(cc, cost - c0);}return cc;
}int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);while (cin >> n >> h >> b && n) {int cc = solve();cout << "Case " << ++kase << ": ";cc < 0 ? cout << "impossible" << endl : cout << cc << endl;}return 0;
}

这篇关于UVa1104/LA5131 Chips Challenge的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1141185

相关文章

USACO Section 1.5 Checker Challenge

题意: N皇后问题  输出  字典序最小的3种解法 和 解的数量 思路: dfs去放皇后判断和前面的皇后是否冲突 题目时间卡的超级很近!!  简单的搜索一定跪  能剪的地方要拼命剪枝!! 列举我的剪枝: 1.直接按字典序搜索  最先搜到的3个解保证字典序最小  直接输出 2.通过上几行皇后的放法  求出现在这行有几个位置能放皇后  之后进行搜索(这是关键!!  千万不要先搜位置

BookSim2 安装步骤教程 Network-on-Chips (NoCs) 片上网络模拟器 含视频

BookSim简介 BookSim2 一个用于Network-on-Chips (NoCs) 芯片上网络的周期精确模拟器。该模拟器的设计是为了实现网络组件的模拟灵活性和精确建模。  BookSim1 是一个通用的网络模拟器,并不专门针对片上环境。不支持在片上网络环境中提出的一些更先进的功能和拓扑结构。 背景 随着集成在单个芯片上的核心和模块数量的不断增加,片上网络正成为现代微处理器不可或缺

vulnhub靶机hacksudoLPE中Challenge-1

下载地址:https://download.vulnhub.com/hacksudo/hacksudoLPE.zip 主机发现 目标146 端口扫描 服务扫描 漏洞扫描 上面那整出来几个洞,可以试试 easy? 估计就是看源码 看来是的 登入咯 这里进不去就是ssh咯 这个看着有点像提权的操作 一、Challenge-1 1.

codechef August Challenge 2014 第五个题目

题意:点击打开链接 题目链接:点击打开链接 思路:入门的状态压缩,如果按照行一行一行下来(选衣服)去选的话状态太多,无法压缩,考虑到题目中n比较小,所以改用按照列一列一列推,把人压缩到二进制里面,1表示这个人已经选了,0表示还没有选,然后递推就可以达到答案! #include<set>#include<queue>#include<cmath>#include<cstdio

The Eudyptula Challenge

What is it? The Eudyptula Challenge is a series of programming exercises for the Linux kernel, that start from a very basic “Hello world” kernel module, moving on up in complexity(复杂) to getting patc

【12月Top 2】MarTech Challenge 点击反欺诈预测

背景 广告欺诈是数字营销需要面临的重要挑战之一,点击会欺诈浪费广告主大量金钱,同时对点击数据会产生误导作用。本次比赛提供了约50万次点击数据。特别注意:我们对数据进行了模拟生成,对某些特征含义进行了隐藏,并进行了脱敏处理。 请预测用户的点击行为是否为正常点击,还是作弊行为。点击欺诈预测适用于各种信息流广告投放,banner广告投放,以及百度网盟平台,帮助商家鉴别点击欺诈,锁定精准真实用户。

ACM-ICPC 2018 南京赛区网络预赛 E AC Challenge(状压DP)

题目链接:https://nanti.jisuanke.com/t/30994   题目大意:有n道题,每道题做出来会得到t*a[i]+b[i]分,但是有些题目有先决条件,需要先完成某些题目才能写,问最多能得到多少分   题目思路:这道题需要用二进制的做法。首先先用二进制表示每道题的先决条件,放入pre数组,第几位是1就是需要先写第几题。然后就把所有的情况全部枚举出来,由于一共就20题,一

mageNet Object Localization Challenge

竞争描述 虽然人们很容易辨别出照片中细微的差别,但电脑仍然有办法。视觉上相似的东西很难让电脑计算,就像这堆重叠的香蕉。 或者想想这张照片,一个狐狸家族伪装在野外-狐狸在哪里结束,草在哪里开始?                                         注释。 由于这种竞争,仅2010年至2014年,图像分类误差就减少了4.2倍(从28.2%降至6.7%),定位误

跟TED演讲学英文:The next grand challenge for AI by Jim Fan

The next grand challenge for AI Link: https://www.ted.com/talks/jim_fan_the_next_grand_challenge_for_ai? Speaker: Jim Fan Date: October 2023 文章目录 The next grand challenge for AIIntroductionVo

The Python Challenge

The Python Challenge 地址:http://www.pythonchallenge.com/ 一共33关 第0关 很明显数字238,但是直接访问提示:No… the 38 is a little bit above the 2… 意思是38在2的上方,就是要2的38次方 运算print(2**38)得到结果 第1关 根据映射关系解密,我直接先去试了凯撒: 将这个