Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #include <cstdio>
- #include <cmath>
- #include <algorithm>
- using namespace std;
- const int MAXN = 1000000;
- vector<vector<int> > g(MAXN), gr(MAXN);
- vector<vector<int> > g_w(MAXN);
- vector<char> used(MAXN);
- vector<int> order;
- vector<long long> sum(MAXN);
- vector<int> comp_by_point(MAXN);
- vector<int> component[MAXN];
- long long dp[MAXN];
- vector<vector<int> > comp_graph(MAXN);
- vector<vector<int> > comp_graph_weight(MAXN);
- int n_component = 0;
- void dfs1(int v) {
- used[v] = true;
- for (size_t i = 0; i<g[v].size(); ++i)
- if (!used[g[v][i]])
- dfs1(g[v][i]);
- order.push_back(v);
- }
- void dfs2(int v) {
- used[v] = true;
- component[n_component].push_back(v);
- comp_by_point[v] = n_component;
- for (size_t i = 0; i<gr[v].size(); ++i)
- if (!used[gr[v][i]])
- dfs2(gr[v][i]);
- }
- long long dfs3(int v)
- {
- long long ans = 0;
- for (int i = 0; i < (int)comp_graph[v].size(); i++)
- {
- if (dp[comp_graph[v][i]] == -1)
- dp[comp_graph[v][i]] = dfs3(comp_graph[v][i]);
- ans = max(ans, dp[comp_graph[v][i]] + comp_graph_weight[v][i]);
- }
- return ans + sum[v];
- }
- long long f(int x)
- {
- /*int l = 0, r = 1e4 * 3;
- while (r > l)
- {
- int m = (r + l + 1) / 2;
- if (m * (m + 1) / 2 < x)
- l = m;
- else
- r = m - 1;
- }*/
- long long l = (int)((-1 + sqrt(1 + 8 * x)) / 2 + 0.00000001);
- return (l + 1)* x - (l * (l + 1) * (2 * l + 1) / 6 + l * (l + 1) / 2) / 2;
- }
- int main()
- {
- int n, m, s;
- cin >> n >> m;
- for (int i = 0; i < m; i++)
- {
- int a, b, w;
- scanf("%d %d %d", &a, &b, &w);
- a--; b--;
- g[a].push_back(b);
- g_w[a].push_back(w);
- gr[b].push_back(a);
- }
- cin >> s;
- s--;
- for (int i = 0; i < MAXN; i++)
- used[i] = false;
- for (int i = 0; i < n; ++i)
- if (!used[i])
- dfs1(i);
- for (int i = 0; i < MAXN; i++)
- used[i] = false;
- for (int i = 0; i < n; ++i) {
- int v = order[n - 1 - i];
- if (!used[v]) {
- dfs2(v);
- n_component++;
- }
- }
- for (int i = 0; i < n_component; i++)
- dp[i] = -1;
- for (int i = 0; i < n; i++)
- {
- for (int j = 0; j < (int)g[i].size(); j++)
- {
- if (comp_by_point[i] == comp_by_point[g[i][j]])
- {
- sum[comp_by_point[i]] += f(g_w[i][j]);
- }
- else
- {
- comp_graph[comp_by_point[i]].push_back(comp_by_point[g[i][j]]);
- comp_graph_weight[comp_by_point[i]].push_back(g_w[i][j]);
- }
- }
- }
- cout << dfs3(comp_by_point[s]) << endl;
- //system("pause");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement