Codeforces 894E
题意：给出$n$个点和$m$条有向边和出发点$fr$，求从$fr$出发可重复走的最大边权和，其中一条边如果走了一次边权就会减去当前走的次数，比如$w=56$，走过一次以后$w=56-1=55$，走过两次以后$w=56-1-2=55-2=53$，边权扣到0为止，0边权的边亦可以走。
考虑如果图中有一个强连通分量，那么这个强连通分量的所有边都可以走完(所有边权都为0)，所以考虑缩点。一个强连通分量的所有对答案贡献转为这个 强连通分量点 的点权。
如何计算边对答案的贡献? 可以二分解决，但是我这里运用了离线，先把所有边权存下来排序，然后一直进行$1+2+3+…$来决定每条边能过多少次及贡献。
然后新图就是一个DAG，在DAG上求个最长路即可，但是这幅图既有边权又有点权，所以不要忘记加上点权。
(btw: 人生第一题CFR div2E)
Codeforces Submission
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
LL n, m;//Input
struct data {
LL x, y;
}ed[1000000 + 5];//原图中的边
struct data2 {
LL x, y, w;
}ed2[1000000 + 5];//新图中的边
struct data3 {
LL no, hw, w;
}wi2[1000000 + 5];//离线处理后的边权
bool cmp1(const data3 &a, const data3 &b) {
return a.w < b.w;
}
bool cmp2(const data3 &a, const data3 &b) {
return a.no < b.no;
}
vector<LL> G[1000000 + 5], R[1000000 + 5];//原图，新图
LL totwi[1000000 + 5];//缩点后每个点的权
LL vis[1000000 + 5], dfn[1000000 + 5], low[1000000 + 5], num[1000000 + 5], tb, en1, en2, totnum, fr, ans;
//访问数组，时间戳数组，最小追溯数组，原图每个点对应新图的强连通分量编号，时间戳计数，原图边计数，新图边计数，一共有多少个scc，输入起点，最后答案
stack<LL> s;//Tarjan的stack，存节点
void ins1(LL x, LL y) {en1++, ed[en1] = (data){x, y}, G[x].push_back(en1);}//在原图插入一个新边
void ins2(LL x, LL y, LL w) {en2++, ed2[en2] = (data2){x, y, w}, R[x].push_back(en2);}//在新图插入一个新边
void tarjan(LL u) {//缩点
low[u] = dfn[u] = ++tb;
vis[u] = -1, s.push(u);
for (LL i = 0; i < (LL)G[u].size(); i++) {
LL v = ed[G[u][i]].y;
if (vis[v] == -1) low[u] = min(low[u], dfn[v]);
else if (vis[v] == 0) tarjan(v), low[u] = min(low[u], low[v]);
}
if (dfn[u] == low[u]) {
LL e;
totnum++;
do {
e = s.top(); s.pop();
num[e] = totnum;
vis[e] = 1;
} while (e != u);
}
}
void rebuild() {
ms(vis, 0);
for (LL i = 1; i <= m; i++) {
if (num[ed[i].x] == num[ed[i].y]) totwi[num[ed[i].y]] += wi2[i].hw;
}//计算强连通分量的边权和
for (LL u = 1; u <= n; u++) {
for (LL i = 0; i < (LL)G[u].size(); i++) {
LL v = ed[G[u][i]].y;
if (num[v] == num[u] || vis[G[u][i]]) continue;
vis[G[u][i]] = true;
ins2(num[u], num[v], wi2[G[u][i]].w);//强连通分量之间的连边
}
}
}
LL dfs(LL u) {
if (vis[u] > 0) return vis[u];
for (LL i = 0; i < (LL)R[u].size(); i++) {
LL v = ed2[R[u][i]].y;
vis[u] = max(vis[u], dfs(v) + ed2[R[u][i]].w + totwi[v]);//要加上点权
}
ans = max(ans, vis[u]);
return vis[u];
}
void clean() {//清除
ans = totnum = en1 = en2 = tb = 0;
for (LL i = 0; i <= n; i++) {
totwi[i] = num[i] = vis[i] = dfn[i] = low[i] = 0;
G[i].clear(), R[i].clear();
}
}
void solve() {
clean();
for (LL x, y, i = 1; i <= m; i++) {
scanf("%I64d%I64d%I64d", &x, &y, &wi2[i].w);
wi2[i].no = i, ins1(x, y);
}
scanf("%I64d", &fr);
LL cnt = 1, i = 1, mdzz = 0, taki = 0;
sort(wi2 + 1, wi2 + 1 + m, cmp1);
while (i <= m) {
mdzz += cnt;
taki += mdzz;
while (mdzz >= wi2[i].w && i <= m) {
wi2[i].hw = wi2[i].w * cnt - (taki - mdzz), i++;
}
cnt++;
}//离线求每条边贡献
sort(wi2 + 1, wi2 + 1 + m, cmp2);
for (LL i = 1; i <= n; i++) if (!vis[i]) tarjan(i);
rebuild();
ms(vis, 0), dfs(num[fr]);
printf("%I64d\n", ans + totwi[num[fr]]);
}
int main() {
scanf("%I64d%I64d", &n, &m), solve();
return 0;
}
