博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ-3469 Dual Core CPU 最小割最大流
阅读量:5821 次
发布时间:2019-06-18

本文共 2236 字,大约阅读时间需要 7 分钟。

  该题是给定对个任务,然后告诉你这多个任务在两个不同的核心上执行任务所花费的不同代价,并且还告诉如果其中一些任务不在同一个核心上面运行的话,还有有多余的开销。最后问我们完成所有任务的最小开销是多少?

  对于这个问题,我们先把问题简单话一下,如果没有第二个约束条件,仅仅只有在两个核上的运行时间。那么可能你会说对每个时间所花费的时间取一个最小值就可以了,事实也确实如此,但是如果用流网络来建立这个模型的话,那么我们需要将这个事件拆成两个点,从源点流向左边点的容量是一个核心上花费的时间,两个事件点之间的容量为无穷大,右边点流向汇点的容量为该事件在第二个核心上面所花费的时间,由于中间的边的容量是无穷大,所以最小割的边集中一定没有这些边,也因此这样选择出来的最小割就是我们所要的答案。

  让我们再将这个问题的难度加大,也即附上题目中所给定的约束,两个事件在不同的核心上处理将带来多余的时间开销,假设输入数据为A, B, T 表示A事件与B事件不再同一核心上面的要多花费T时间,那么我们为一个事件再添加两条路径(用 A, A' 表示左右两个事件点),从 A -(T)-> B -(INF)->A' 以及 B -(T)-> A -(INF)->B',这样相当与给了整个时间更多的选择,此时求出来的最小割即为我们想要的最小值。

  代码如下:

#include 
#include
#include
#include
#include
#define RE(x) ((x)^1)#define CP(x) ((x)+20000)#define INF 0x3fffffffusing namespace std;int N, M, dis[40005], idx = -1, head[40005];const int source = 0, sink = 40001;struct Edge{ int v, cap, next;}e[1000000]; // 100万条边void insert(int a, int b, int c){ ++idx; e[idx].v = b, e[idx].cap = c; e[idx].next = head[a], head[a] = idx;}bool bfs(){ int u; queue
q; memset(dis, 0xff, sizeof (dis)); dis[source] = 0; q.push(source); while (!q.empty()) { u = q.front(); q.pop(); for (int i = head[u]; i != -1; i = e[i].next) { if (dis[e[i].v] == -1 && e[i].cap > 0) { dis[e[i].v] = dis[u] + 1; q.push(e[i].v); } } } return dis[sink] != -1;}int dfs(int u, int flow){ if (u == sink) { return flow; } int tf = 0, sf; for (int i = head[u]; i != -1; i = e[i].next) { if (dis[u]+1 == dis[e[i].v] && e[i].cap > 0 && (sf = dfs(e[i].v, min(flow-tf, e[i].cap)))) { e[i].cap -= sf, e[RE(i)].cap += sf; tf += sf; if (tf == flow) { return flow; } } } if (!tf) { dis[u] = -1; // 剪枝 } return tf;}int dinic(){ int ans = 0; while (bfs()) { ans += dfs(source, INF); } return ans;}int main(){ int a, b, c; memset(head, 0xff, sizeof (head)); scanf("%d %d", &N, &M); for (int i = 1; i <= N; ++i) { scanf("%d %d", &a, &b); insert(source, i, a); insert(i, source, 0); insert(i, CP(i), INF); insert(CP(i), i, 0); insert(CP(i), sink, b); insert(sink, CP(i), 0); } for (int i = 1; i <= M; ++i) { scanf("%d %d %d", &a, &b, &c); insert(a, b, c); insert(b, a, c); insert(a, CP(b), INF); insert(b, CP(a), INF); } printf("%d\n", dinic()); return 0;}

转载地址:http://mnbdx.baihongyu.com/

你可能感兴趣的文章
用计算器计算“异或CRC”
查看>>
让你的WPF程序在Win7下呈现Win8风格主题
查看>>
JDBC二查询(web基础学习笔记八)
查看>>
监听器(web基础学习笔记二十二)
查看>>
802.11 学习笔记
查看>>
Leetcode-Database-176-Second Highest Salary-Easy(转)
查看>>
构建Docker Compose服务堆栈
查看>>
最小角回归 LARS算法包的用法以及模型参数的选择(R语言 )
查看>>
Hadoop生态圈-Kafka常用命令总结
查看>>
如何基于Redis Replication设计并实现Redis-replicator?
查看>>
Linux 环境下 PHP 扩展的编译与安装 以 mysqli 为例
查看>>
浮点数内存如何存储的
查看>>
贪吃蛇
查看>>
EventSystem
查看>>
用WINSOCK API实现同步非阻塞方式的网络通讯
查看>>
玩一玩博客,嘿嘿
查看>>
P1352 没有上司的舞会
查看>>
ios11文件夹
查看>>
【HLOJ 559】好朋友的题
查看>>
Electric Fence(皮克定理)
查看>>