题解 P2656 【采蘑菇】
Ireliaღ
2019-07-19 09:41:31
**Tarjan缩点+拆点+Spfa最长路**
## 解题思路
- 缩点。显然，进入一个强连通分量，可以把里面的边全部**走满**
- 拆点，分为入点和出点
- 建图
- 对于不同强连通分量的边，正常建，边权为**走一次**的边权，注意是入点连出点
- 对于相同强连通分量的边，把**走满**的边权加到连接这个点入点和出点的边权上
- 从起点的入点`Spfa`最长路，就可以不用考虑点权了。然后在所有出点中找距离最长的。
## 代码
```cpp
#include <iostream>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
const int MAXN = 8e4 + 5;
const int MAXM = 2e5 + 5;
struct Edge{
int to, val;
Edge *nxt;
Edge(int to, int val, Edge *nxt) : to(to), val(val), nxt(nxt) {}
};
Edge *hd1[MAXN], *hd2[MAXN];
void Add1(int u, int v, int w) {
hd1[u] = new Edge(v, w, hd1[u]);
}
void Add2(int u, int v, int w) {
hd2[u] = new Edge(v, w, hd2[u]);
}
int n, m;
int inx[MAXM], iny[MAXM], inz[MAXM];
double inr[MAXM];
int low[MAXN], col[MAXN], dfn[MAXN], tc, tot;
stack<int> stk;
int w[MAXN << 1], dis[MAXN << 1];
bool vis[MAXN << 1];
void Tarjan(int u) {
stk.push(u); dfn[u] = low[u] = ++tc;
for (Edge *e = hd1[u]; e; e = e->nxt) {
int v = e->to;
if (!dfn[v]) {
Tarjan(v);
low[u] = min(low[u], low[v]);
} else {
if (!col[v]) low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
col[u] = ++tot;
while (!stk.empty()) {
int v = stk.top(); stk.pop();
col[v] = tot;
if (v == u) break;
}
}
}
int GetTotal(int x, double y) {
int ret = 0;
while (x) {
ret += x;
x = (int)floor((double)x * y);
}
return ret;
}
int Id(int u, int typ) {
if (typ == 0) return col[u];
else return col[u] + tot;
}
void Rebuild() {
for (int i = 1; i <= m; i++) {
if (col[inx[i]] == col[iny[i]]) w[col[inx[i]]] += GetTotal(inz[i], inr[i]);
else Add2(Id(inx[i], 1), Id(iny[i], 0), inz[i]);
}
for (int i = 1; i <= tot; i++) Add2(i, i + tot, w[i]);
}
void Spfa(int s) {
memset(dis, 0x8f, sizeof(dis));
queue<int> q; q.push(s); dis[s] = 0; vis[s] = true;
while (!q.empty()) {
int u = q.front(); q.pop(); vis[u] = false;
for (Edge *e = hd2[u]; e; e = e->nxt) {
int v = e->to;
if (dis[v] < dis[u] + e->val) {
dis[v] = dis[u] + e->val;
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> inx[i] >> iny[i] >> inz[i] >> inr[i];
Add1(inx[i], iny[i], inz[i]);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) Tarjan(i);
}
for (int i = 1; i <= n; i++) {
cerr << col[i] << ' ';
}
cerr << endl;
Rebuild();
int s;
cin >> s;
Spfa(Id(s, 0));
int ans = 0;
for (int i = 1; i <= tot * 2; i++) ans = max(ans, dis[i]);
cout << ans << endl;
return 0;
}
```