首页 技术 正文
技术 2022年11月23日
0 收藏 463 点赞 4,908 浏览 2233 个字

http://acm.hdu.edu.cn/showproblem.php?pid=3879

http://www.lydsy.com/JudgeOnline/problem.php?id=1497

题意:给出n个点m条边,其中每个点有一个权值代表修建这个点需要耗费的钱,然后m条边里面,代表如果两个修建好的点相连的话,那么可以得到一点利润。求最大的获利。

思路:和BZOJ 1497是同一道题目。学习最大权闭合图的题目,看了一下不清楚应该怎么建图,然后只好搜一个论文来看看。http://wenku.baidu.com/view/6507a6fe2cc58bd63186bdaf.html

建图:将S与n个点相连,权值为点权,将m条边当成点与T相连,权值为边权,边的两个顶点分别再和化成点的边相连,权值为INF。

闭合图可以解决一些依赖关系,例如这道题目需要有两个顶点才可以得到一条边,边是依赖于两个顶点的形成的。

于是网络是这样的:S->站的点->边的点->T。

我们对这个网络得到的一个割 = 选择的站的花费 + 未选择的边的利润(也可以看作损失的利润),显然这个割集越小越好,即最小割。我们要求的是答案 = 选择的边的利润 – 选择的站的利润。

那么我们一开始可以先累加得到一个选择所有边的利润tot,那么恰好tot – 最小割 = 选择所有边的利润 – 未选择边的利润 – 选择的站的花费 = 选择的边的利润 – 选择的站的利润 = 答案。

所以跑一遍最大流后就用tot – 最大流就可以得到答案了。

记得边的数组要开大一点。

 #include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define N 60010
#define M 350010 // 30w不过
struct Edge {
int u, v, nxt, cap;
Edge () {}
Edge (int u, int v, int nxt, int cap) : u(u), v(v), nxt(nxt), cap(cap) {}
} edge[M];
int head[N], tot, S, T, cur[N], dis[N], gap[N], pre[N]; void Add(int u, int v, int cap) {
edge[tot] = Edge(u, v, head[u], cap); head[u] = tot++;
edge[tot] = Edge(v, u, head[v], ); head[v] = tot++;
} void BFS() {
queue<int> que;
que.push(T);
memset(dis, INF, sizeof(dis));
memset(gap, , sizeof(gap));
gap[]++; dis[T] = ;
while(!que.empty()) {
int u = que.front(); que.pop();
for(int i = head[u]; ~i; i = edge[i].nxt) {
if(dis[edge[i].v] != INF) continue;
dis[edge[i].v] = dis[u] + ;
gap[dis[edge[i].v]]++;
que.push(edge[i].v);
}
}
} int ISAP(int n) {
BFS();
memcpy(cur, head, sizeof(cur));
int u = pre[S] = S, flow, ans = , index, i;
while(dis[S] < n) {
if(u == T) {
flow = INF;
for(i = S; i != T; i = edge[cur[i]].v)
if(flow > edge[cur[i]].cap) flow = edge[cur[i]].cap, index = i;
for(i = S; i != T; i = edge[cur[i]].v)
edge[cur[i]].cap -= flow, edge[cur[i]^].cap += flow;
u = index; ans += flow;
}
for(i = cur[u]; ~i; i = edge[i].nxt) if(edge[i].cap && dis[edge[i].v] + == dis[u]) break;
if(~i) { cur[u] = i; pre[edge[i].v] = u; u = edge[i].v; }
else {
if(--gap[dis[u]] == ) break;
int md = n + ;
for(i = head[u]; ~i; i = edge[i].nxt)
if(edge[i].cap && dis[edge[i].v] < md) md = dis[edge[i].v], cur[u] = i;
gap[dis[u] = md + ]++;
u = pre[u];
}
}
return ans;
} int main() {
int n, m;
while(~scanf("%d%d", &n, &m)) {
memset(head, -, sizeof(head));
tot = ; S = ; T = n + m + ;
for(int i = ; i <= n; i++) {
int w; scanf("%d", &w);
Add(S, i, w); // 源点和站点相连
}
int tot = ;
for(int i = ; i <= m; i++) {
int a, b, c;
scanf("%d%d%d",&a, &b, &c);
tot += c; // 选择边的利润和
Add(i + n, T, c); // 边的点和汇点相连
Add(a, i + n, INF);
Add(b, i + n, INF);
}
printf("%d\n", tot - ISAP(T + ));
}
return ;
}
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:8,933
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,454
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,267
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,085
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,716
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:4,753