题解：AtCoder Beginner Contest AT_abc373_d ABC373D Hidden Weights（格式美化版）

题目传送门

题目翻译

给你一个 $N$ 个点，$M$ 条边的有向图，其中边有边权。现在让你给每一个点设置一个点权 $a$，使得对于任意两点 $x$ 和 $y$，如果 $x$ 到 $y$ 有一条边，边权为 $w$，那么需要满足 $a_y-a_x=w$。现在让你输出一组合法的分配方案，题目保证存在，输出任意一组都行。

思路1（注意拿不到满分）

题目让满足 $a_y-a_x=w$，不就是要满足 $a_y-a_x\le w$ 且 $a_x-a_y\le -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函数给替换掉了。

1. 建图代码没有变化，但是意义变了。从 $x$ 到 $y$ 连一条权值为 $w$ 边表示 $a_y-a_x=w$。
   代码：

   add(x, y, w);
   add(y, x, -w);
   

2. 我们得想方设法替换掉SPFA。于是想到了深搜DFS：

   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);
   }
   }
   

   在这里，我们用 $vis$ 数组记录这个点的点权有没有被算过，用 $dis$ 来记录点权。

完整代码如下：

#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;
} 

原文地址：https://blog.csdn.net/ArmeriaLeap/article/details/142670159

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！