P2656 采蘑菇

題意：

有n個點，m個單向邊，每個邊都有邊權，如果經過這個邊，可以獲得其邊權，而其邊權會變成原來的p倍(0.1<=p<=0.8)，向下取整
從s點出發，問最多可以采到的蘑菇

題解：

因為是單向邊，除非出現一個環，不然每個邊最多只能走一次，如果有一個環，環上的邊權可以一直獲取，直到邊權為0.
所以我們可以用tarjan進行縮點，將這個環上所有得到的價值加起來，賦給縮成的點x。
縮完點后，就同時有點權(在之前環上所能獲取的價值)和邊權，且無環，那直接跑一個拓撲+dp就可以，在拓撲過程中轉移dp,然后取最大即可
總結：tarjan縮點+拓撲dp

代碼：

// Problem: P2656 采蘑菇 // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P2656 // Memory Limit: 125 MB // Time Limit: 1000 ms // By Jozky#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime= clock();freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn= 3e5 + 9; double hui[maxn]; int n, m; struct node{int v,w;double k; }; vector<node>vec[maxn]; int dfn[maxn], low[maxn], vis[maxn]; int color[maxn]; int tot= 0, col= 0; int degree[maxn]; vector<PII> vec2[maxn]; vector<int> co[maxn]; int newa[maxn]; stack<int> s; void tarjan(int x) {vis[x]= 1;dfn[x]= low[x]= ++tot;s.push(x);for (auto it : vec[x]) {int v= it.v;int w= it.w;if (!dfn[v]) {tarjan(v);low[x]= min(low[x], low[v]);}else if (vis[v]) {low[x]= min(low[x], dfn[v]);}}if (dfn[x] == low[x]) {col++;while (1) {int top= s.top();s.pop();color[top]= col;vis[top]= 0;if (top == x)break;}} } int dp[maxn]; void solve() {for (int i= 1; i <= n; i++) {if (!dfn[i])tarjan(i);}for (int i= 1; i <= n; i++) {for (auto it : vec[i]) {int v= it.v;int w= it.w;double k=it.k;if (color[i] != color[v]) {degree[color[v]]++;vec2[color[i]].push_back({color[v], w});}else {while(w){newa[color[v]]+=w;w=w*k/10;}}}} } void troop(int s) {queue<int> q;for(int i=1;i<=col;i++){if(!degree[i])q.push(i);dp[i]=-INF_int;}dp[color[s]]=newa[color[s]];q.push(s);while (!q.empty()) {int u= q.front();q.pop();for (auto it : vec2[u]) {int v= it.first;int w= it.second;degree[v]--;dp[v]= max(dp[v], dp[u] + newa[v] + w);if (!degree[v])q.push(v);}} } int main() {rd_test();read(n, m);for (int i= 1; i <= m; i++) {int u, v, w;double s;scanf("%d%d%d%lf", &u, &v, &w, &s);vec[u].push_back({v, w,s*10});}int s;read(s);solve();troop(s);int maxx= 0;for (int i= 1; i <= col; i++)maxx= max(dp[i], maxx);cout << maxx;//Time_test(); } //92

總結

以上是生活随笔為你收集整理的P2656 采蘑菇的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。