1737: 太空飞行计划问题——最大权闭合子图

1737: 太空飞行计划问题——最大权闭合子图

题意：

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业 性实验而获取利润。现已确定了一个可供选择的实验集合E={E1，E2，…，Em}，和进行这 些实验需要使用的全部仪器的集合I={I1，I2，…In}。实验Ej需要用到的仪器是I的子集Rj。 配置仪器Ik的费用为ck美元。实验Ej的赞助商已同意为该实验结果支付pj美元。W教授的 任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才 能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部 费用的差额。 «编程任务： 对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。

思路：

最大权闭合图模板题。从起点往每个权值为正的点建立一条边，容量为点权值。，每个权值为负的点往终点建立一条边，容量为权值的绝对值，如果选A就必须选B 则就从A建立一条往B的边，容量为正无穷。

然后正权值加起来减去最大流（最小割）就是能选出来最大权闭合图所有点加起来的值。

最大权闭合图的点就是从起点开始广搜，权值为0的点不走，能走到的点就是被选中的点。

#include #include #include #include #include #include using namespace std;const int maxn = 500;const int INF = 0x3f3f3f3f;struct Edge { int from, to, cap, flow;};struct Dinic { int s, t; vector edges; vector G[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; void init() { edges.clear(); for (int i = 0; i < maxn; i++) G[i].clear(); } void addedge(int from, int to, int cap) { edges.push_back(Edge{from, to, cap, 0}); edges.push_back(Edge{to, from, 0, 0}); int m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool bfs() { memset(vis, 0, sizeof(vis)); queue q; q.push(s); d[s] = 0; vis[s] = 1; while (!q.empty()) { int x = q.front(); q.pop(); for (int i = 0; i < G[x].size(); i++) { Edge &e = edges[G[x][i]]; if (!vis[e.to] && e.cap > e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; q.push(e.to); } } } return vis[t]; } int dfs(int x, int a) { if (x == t || a == 0) return a; int flow = 0, f; for (int &i = cur[x]; i < G[x].size(); i++) { Edge &e = edges[G[x][i]]; if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) { e.flow += f; edges[G[x][i]^1].flow -= f; flow += f; a -= f; if (a == 0) break; } } return flow; } int maxflow(int s, int t) { this->s = s, this->t = t; int flow = 0; while (bfs()) { memset(cur, 0, sizeof(cur)); flow += dfs(s, INF); } return flow; }}ac;int main(){ int m, n; scanf("%d%d", &m, &n); ac.init(); int s = 0, t = n + m + 1; int sum = 0; int C; char c; for (int i = 1; i <= m; i++) { scanf("%d", &C); ac.addedge(s, i, C); sum += C; int j; while ((c = getchar()) != '\n') { scanf("%d", &j); ac.addedge(i, j+m, INF); } } for (int i = 1; i <= n; i++) { scanf("%d", &C); ac.addedge(i+m, t, C); } int maxf = ac.maxflow(s, t); for (int i = 1; i <= m; i++) { if (ac.vis[i]) printf("%d ", i); } printf("\n"); for (int i = m+1; i <= m+n; i++) { if (ac.vis[i]) printf("%d ", i-m); } printf("\n%d\n", sum - maxf); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。