【35.00%】【z13】【b093】最优贸易

最优贸易"/>

【35.00%】【z13】【b093】最优贸易

【题解】
这题就是要在n个点里面选一个花费最小的点。然后找一个花费最大的点。两者之差为最大值。
但是最大值的点要在最小值的点之后出现。且走到后者之后要能够到达N号节点。为了处理掉环。先用tarjan进行缩点。这样整张图就不会出现环了。接下来进行DP即可。记录到达某个点之前所能买到的最低价格。然后尝试在这个点卖掉。记录最优值。然后把最优值一直往后传。最后输出f[n]。这里的DP用了记忆化搜索。或者说是一个强力剪枝。自己看吧。
【代码】

//#pragma comment(linker,"/STACK:102400000,102400000")
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>using namespace std;const int MAXN = 100000 + 100;struct data2
{int sell, min;
};int n, m, dx = 0, nn = 0, bh[MAXN];
int price[MAXN], dfn[MAXN], low[MAXN], ma_x[MAXN], mi_n[MAXN], ans = 0;
data2 f[MAXN];
vector <int> a[MAXN], aa[MAXN];
stack <int> z;
int zzz[MAXN];
bool flag[MAXN] = { 0 };
bool used[MAXN] = { 0 };void tarjan(int x)
{flag[x] = true;dfn[x] = low[x] = ++dx;zzz[x] = z.size();z.push(x);int len = a[x].size();for (int i = 0; i <= len - 1; i++){int y = a[x][i];if (!flag[y]){tarjan(y);low[x] = min(low[x], low[y]);}elseif (zzz[y] >0)low[x] = min(low[x], dfn[y]);}if (low[x] == dfn[x]){nn++;int tma = price[x], tmi = price[x], limit = zzz[x];while (z.size() != limit){int t = z.top();tma = max(tma, price[t]);tmi = min(tmi, price[t]);bh[t] = nn;zzz[t] = 0;z.pop();}ma_x[nn] = tma;mi_n[nn] = tmi;}
}void dfs(int now, int pre)
{bool can = false; //这个can表示这个点有没有更新。如果没有更新任何东西就剪枝if (f[now].min > f[pre].min){f[now].min = f[pre].min;can = true;}if (f[now].min > mi_n[now]){f[now].min = mi_n[now];can = true;}if (f[now].sell < ma_x[now] - f[pre].min){f[now].sell = ma_x[now] - f[pre].min;can = true;}if (f[now].sell < ma_x[now] - mi_n[now]){f[now].sell = ma_x[now] - mi_n[now];can = true;}if (f[now].sell < f[pre].sell)//答案往后传{f[now].sell = f[pre].sell;can = true;}if (!can)return;int len = aa[now].size();for (int i = 0; i <= len - 1; i++)if (!used[aa[now][i]]){used[aa[now][i]] = true;dfs(aa[now][i], now);used[aa[now][i]] = false;}
}int main()
{//freopen("F:\\rush.txt", "r", stdin);scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++)scanf("%d", &price[i]);for (int i = 1; i <= m; i++){int x, y, z;scanf("%d%d%d", &x, &y, &z);a[x].push_back(y);if (z == 2) a[y].push_back(x);}tarjan(1);for (int i = 1; i <= n; i++)if (bh[i] != 0)//bh数组记录了缩点后i号点新的编号{int len = a[i].size();for (int j = 0; j <= len - 1; j++){int y = a[i][j];if (bh[y] != 0 && bh[i] != bh[y])aa[bh[i]].push_back(bh[y]);}}for (int i = 1; i <= nn; i++)f[i].min = 2100000000;int qidian = bh[1];//从起点开始dfs+dpused[qidian] = true;f[qidian].min = mi_n[qidian];//一开始就可能在环里面f[qidian].sell = ma_x[qidian] - mi_n[qidian];int len = aa[qidian].size();for (int i = 0; i <= len - 1; i++)if (!used[aa[qidian][i]]){used[aa[qidian][i]] = true;dfs(aa[qidian][i], qidian);used[aa[qidian][i]] = false;}printf("%d\n", f[bh[n]].sell);return 0;
}

转载于:.html