题目翻译
给你一个 N N N 个点， M M M 条边的有向图，其中边有边权。现在让你给每一个点设置一个点权 a a a，使得对于任意两点 x x x 和 y y y，如果 x x x 到 y y y 有一条边，边权为 w w w，那么需要满足 a y − a x = w a_y-a_x=w ay−ax=w。现在让你输出一组合法的分配方案，题目保证存在，输出任意一组都行。
思路1（注意拿不到满分）
题目让满足 a y − a x = w a_y-a_x=w ay−ax=w，不就是要满足 a y − a x ≤ w a_y-a_x \le w ay−ax≤w 且 a x − a y ≤ − w a_x-a_y \le -w ax−ay≤−w 吗？差分约束板子！可以参考 这道题。
代码如下：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
typedef long long LL;
int n, m;
LL dis[200010];
int vis[200010];
struct edge
{
int y, w;
} ;
vector<edge> g[200010];
void add(int x, int y, int w)
{
g[x].push_back((edge){y, w});
}
void spfa(int s)
{
queue<int> q;
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
q.push(s);
dis[s] = 0;
vis[s] = 1;
while (q.size())
{
int x = q.front();
q.pop();
vis[x] = 0;
for (int i = 0; i < g[x].size(); i++)
{
int y = g[x][i].y;
int w = g[x][i].w;
if (dis[y] > dis[x] + w)
{
dis[y] = dis[x] + w;
if (vis[y] == 0)
{
q.push(y);
vis[y] = 1;
}
}
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y, w;
cin >> x >> y >> w;
add(x, y, w);
add(y, x, -w);
}
for (int i = 1; i <= n; i++)
add(0, i, 0);
spfa(0);
for (int i = 1; i <= n; i++)
cout << dis[i] << " ";
cout << endl;
return 0;
}
但是，恭喜你T了一个点！其实这个点貌似是专门用来卡SPFA的，所以说优化就不太现实了，换思路吧。
思路2（正解）
前面的逻辑其实没问题，所以我们不用完全推翻重新写，只是把那个SPFA函数给替换掉了。
- 建图代码没有变化，但是意义变了。从
x
x
x 到
y
y
y 连一条权值为
w
w
w 边表示
a
y
−
a
x
=
w
a_y-a_x=w
ay−ax=w。
代码：add(x, y, w); add(y, x, -w); - 我们得想方设法替换掉SPFA。于是想到了深搜DFS：
在这里，我们用 v i s vis vis 数组记录这个点的点权有没有被算过，用 d i s dis dis 来记录点权。void dfs(int x, LL d) { vis[x] = 1; dis[x] = d; for (int i = 0; i < g[x].size(); i++) { int y = g[x][i].y; int w = g[x][i].w; if (!vis[y]) dfs(y, d + w); } }
完整代码如下：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
typedef long long LL;
int n, m;
LL dis[200010];
int vis[200010];
struct edge
{
int y, w;
} ;
vector<edge> g[200010];
void add(int x, int y, int w)
{
g[x].push_back((edge){y, w});
}
void dfs(int x, LL d)
{
vis[x] = 1;
dis[x] = d;
for (int i = 0; i < g[x].size(); i++)
{
int y = g[x][i].y;
int w = g[x][i].w;
if (!vis[y]) dfs(y, d + w);
}
}
void solve()
{
for (int i = 1; i <= n; i++)
if (!vis[i]) dfs(i, 0);
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++)
{
int x, y, w;
scanf("%d %d %d", &x, &y, &w);
add(x, y, w);
add(y, x, -w);
}
solve();
for (int i = 1; i <= n; i++)
printf("%lld ", dis[i]);
printf("\n");
return 0;
}