[洛谷]P2648 赚钱（点权转化为边权+spfa+超级源点）

**赚钱**

**题目描述**

在一个由 $n$ 个城市组成的图中，每个城市都有一个权值。每次行走到相邻城市的成本为1。现在，给定了 $m$ 条边，每条边都有一个权值和一个点权。如果我们从某个城市出发，经过一系列的城市，然后回到起始城市，我们可以获得相应的总点数。

**任务**

求出从每个城市出发，经过一系列的城市，然后回到起始城市所能获得的最大总点数。

**思路**

这个问题可以使用 Dijkstra 算法来解决。我们首先将所有城市的权值都加上1，这样就变成了一个标准的最短路径问题。然后，我们使用 Dijkstra 算法找到从每个城市出发到达其他城市所需的最短距离。

**超级源点**

在这个算法中，我们需要找到一个超级源点，即一个城市，它可以到达所有其他城市。我们可以通过检查每个城市是否能到达所有其他城市来实现这一点。如果某个城市不能到达所有其他城市，那么它就不是超级源点。

**代码示例**

cpp#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int N =100010;
typedef long long ll;

struct Edge {
 int to, next;
};

int n, m, s, t;
ll dis[N];
Edge e[N << 1];

void add(int u, int v) {
 e[m].to = v;
 e[m].next = head[u];
 head[u] = m++;
}

int head[N], tot;

void init() {
 for (int i =0; i <= n; i++) {
 dis[i] =1e18;
 head[i] = -1;
 }
 tot =0;
}

bool spfa() {
 queue<int> q;
 for (int i =0; i <= n; i++)
 if (dis[i] ==1e18)
 dis[i] =0, q.push(i);
 while (!q.empty()) {
 int u = q.front();
 q.pop();
 for (int i = head[u]; ~i; i = e[i].next) {
 int v = e[i].to;
 if (dis[v] > dis[u] +1) {
 dis[v] = dis[u] +1;
 if (!q.empty() && q.front() == v)
 q.pop();
 q.push(v);
 }
 }
 }
 return dis[t] !=1e18;
}

ll dfs(int u, ll flow) {
 if (u == t || !flow)
 return flow;
 ll res =0;
 for (int i = head[u]; ~i; i = e[i].next) {
 int v = e[i].to;
 if (dis[v] == dis[u] +1 && e[i].next != -1) {
 ll tmp = dfs(v, min(flow, e[i].next));
 res += tmp;
 flow -= tmp;
 e[i].next -= tmp;
 e[i ^1].next += tmp;
 if (!flow)
 return res;
 }
 }
 return res;
}

ll dinic() {
 ll res =0;
 while (spfa())
 res += dfs(s,1e18);
 return res;
}

cppbool is_super_source(int u) {
 for (int i = head[u]; ~i; i = e[i].next)
 if (!vis[e[i].to])
 return false;
 return true;
}

void find_super_source() {
 vis.assign(n +1, false);
 super_source = -1;
 for (int i =0; i <= n; i++)
 if (is_super_source(i))
 super_source = i;
}

cppll dinic_with_super_source() {
 ll res =0;
 while (spfa()) {
 for (int i = head[super_source]; ~i; i = e[i].next)
 if (!vis[e[i].to])
 vis[e[i].to] = true, res += dfs(e[i].to,1e18);
 vis.assign(n +1, false);
 }
 return res;
}

cppint main() {
 init();
 // ...
 find_super_source();
 ll ans = dinic_with_super_source();
 cout << ans << endl;
 return0;
}