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

P2762 太空飞行计划问题 (网络流、最大权闭合子图问题)

news 来源：原创 2025/9/5 9:20:01

P2762 太空飞行计划问题

思路：

今日网络流
这个题思路其实很简单，先说结论：源点连所有实验，容量为收益；实验连接对应仪器，容量为无穷；所有仪器连汇点，容量为费用（注意是正权）。这是一个非常符合常理的建图方式，但为什么这样建图能求出结果呢？
最大流不好理解，可以先考虑最小割。由于实验到仪器的边容量为无穷，所以最小割不可能在中间，只可能在 $s$ 到实验或仪器到 $t$ 的边上。
最小割如果在 $s$ -实验之间，说明这个实验不需要选，如果在仪器到t之间的边上，说明这个仪器需要选择。最后所有实验的总收益减去最大流得到的就是利润。

观察这两个图，图1是明显亏本的实验，最小割在 $s$ -实验1，最大流为10，说明实验1不需要选，利润为0。
图2最小割为仪器到 $t$ 的这三条边，说明三个仪器都需要选，最大流为18，最大利润为35-18=17。
最大流的含义可以自己理解，如果选择一个收益为x的实验没有好处，那么最大流里这个实验的贡献就是x，减去后得到的利润中就相当于没选这个实验。
这个问题其实是最大权闭合子图问题，这里有详细的证明。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define pb push_back
#define pii pair<int, int>
#define FU(i, a, b) for (int i = (a); i <= (b); ++i)
#define FD(i, a, b) for (int i = (a); i >= (b); --i)const int inf = 1e18;      // 表示无穷大的容量
const int maxn = 1e5 + 10; // 最大节点数
vector<int> ans1, ans2;// 边的结构体
struct edge {int from, to; // 边的起点和终点int cap;      // 边的容量int flow;     // 边当前的流量edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};// Dinic算法实现类
struct Dinic {int n, m;           // 节点数、边数int s, t;           // 源点、汇点vector<edge> edges; // 所有边的集合，边数两倍（包含反向边）vector<int> G[maxn]; // 邻接表，G[i]保存节点i的所有边在edges中的索引bool vis[maxn]; // BFS使用的访问标记数组int d[maxn];    // 层次网络中各节点的层次（距离）int cur[maxn]; // 当前弧优化数组，记录每个节点当前处理的边void init(int n) { // 初始化，n为节点数this->n = n;for (int i = 0; i < n; i++)G[i].clear();edges.clear();}// 清空所有边的流量，用于多次计算不同流的情况void clear() {for (int i = 0; i < edges.size(); i++)edges[i].flow = 0;}// 将边的容量减去已使用的流量，用于调整残余网络void reduce() {for (int i = 0; i < edges.size(); i++)edges[i].cap -= edges[i].flow;}// 添加一条从from到to，容量为cap的有向边及其反向边void addedge(int from, int to, int cap) {edges.push_back(edge(from, to, cap, 0)); // 正向边，初始流量0edges.push_back(edge(to, from, 0, 0)); // 反向边，初始容量0，流量0m = edges.size();G[from].push_back(m - 2); // 记录正向边在edges中的索引G[to].push_back(m - 1);   // 记录反向边在edges中的索引}// BFS构建层次网络，返回是否存在从s到t的路径bool BFS() {memset(vis, 0, sizeof(vis));queue<int> Q;Q.push(s); // 源点入队vis[s] = true;d[s] = 0;while (!Q.empty()) {int x = Q.front();Q.pop();for (int i = 0; i < G[x].size(); i++) { // 遍历x的所有邻接边edge &e = edges[G[x][i]];// 若边的终点未访问，且仍有剩余容量if (!vis[e.to] && e.cap > e.flow) {vis[e.to] = true;d[e.to] = d[x] + 1; // 层次+1Q.push(e.to);}}}return vis[t]; // 返回汇点是否可达}// DFS寻找增广路径，x为当前节点，a为当前路径上的最小剩余容量int DFS(int x, int a) {if (x == t || a == 0) // 若到达汇点或剩余容量为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; // 剩余容量为0，无需继续搜索}}if (flow == 0)d[x] = -2; // 炸点优化return flow;}// 计算从s到t的最大流int Maxflow(int s, int t) {this->s = s;this->t = t;int flow = 0;while (BFS()) {                  // 每次BFS构建层次网络memset(cur, 0, sizeof(cur)); // 重置当前弧flow += DFS(s, inf);         // 进行多路增广，累加流量}return flow;}// 返回ansvoid getans() {vector<int> ans;for (int i = 0; i < edges.size(); i++) {edge &e = edges[i];if (!(vis[e.from] && !vis[e.to] && e.cap > 0 )&& e.from==s){ans1.pb(e.to-50);}else if (vis[e.from] && !vis[e.to] && e.cap > 0 && e.to==t)ans2.push_back(e.from);}}
} dinic;int w[55], c[55];
signed main() {
#ifdef ONLINE_JUDGE
#elsefreopen("../in.txt", "r", stdin);
#endifint sum = 0;dinic.init(200);int m, n, s = 101, t = 102;cin >> m >> n;for (int i = 1; i <= m; i++) { // 实验51-100cin >> w[i];sum += w[i];dinic.addedge(s, i + 50, w[i]);char tools[10000];memset(tools, 0, sizeof tools);cin.getline(tools, 10000);int ulen = 0, tool;while (sscanf(tools + ulen, "%d", &tool) == 1) // 之前已经用scanf读完了赞助商同意支付该实验的费用{ // tool是该实验所需仪器的其中一个dinic.addedge(i + 50, tool, inf);// 这一行，你可以将读进来的编号进行储存、处理，如连边。if (tool == 0)ulen++;else {while (tool) {tool /= 10;ulen++;}}ulen++;}}for (int i = 1; i <= n; i++) {cin >> c[i];dinic.addedge(i, t, c[i]);}int maxflow = dinic.Maxflow(s, t);dinic.getans();for (int e : ans1)cout << e << " ";cout << endl;for (int e : ans2)cout << e << " ";cout << endl;cout << sum - maxflow << endl;return 0;
}

思路：

代码：

相关文章：