博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
ZJOI2002昂贵的聘礼题解
阅读量:7003 次
发布时间:2019-06-27

本文共 2206 字,大约阅读时间需要 7 分钟。

  • 题目大意

    一个部落,你能够和社会地位等级的极差不大于M的全部人交易。你能够拿金币直接从一个人手里买东西,也能够从别人那里买到那个人想要的东西来获取减价。

    问终于从酋长那里“买”到你心仪的“东西”的最小代价。

  • 题解

    把自己作为起点。向每个物品连边权为这件物品原价的有向边。然后假设买物品i会使物品j降价,那么连一条从i到j边权为降价后的价格的有向边。然后枚举包含了酋长等级的全部等级范围,从自己到酋长的“东西”跑仅仅经过当前等级范围同意的最短路,再取最小值就可以。

    多组数据处理时要把原图清干净。

  • Code

#include 
#include
#include
#include
#include
using namespace std;const int maxn = 100000, nil = 0, oo = 1000000000;int M, N, S, T, ans;int e, nxt[maxn], u[maxn], v[maxn], w[maxn], pnt[150];int d[150];bool vis[150];struct things{ int n, p, m; things(int n = 0, int p = 0, int m = 0) :n(n), p(p), m(m) {}}sth[150];vector
rep[150];struct node{ int n, dis; node(int n = 0, int dis = 0) :n(n), dis(dis) {} bool operator < (const node& b) const { return dis > b.dis; }};void addedge(int a, int b, int c){ u[++e] = a; v[e] = b; w[e] = c; nxt[e] = pnt[a]; pnt[a] = e;}void init(){ int P, L, X, Tt, V; e = 0; ans = oo; memset(nxt, 0, sizeof(nxt)); memset(pnt, 0, sizeof(pnt)); memset(u, 0, sizeof(u)); memset(v, 0, sizeof(v)); memset(w, 0, sizeof(w)); for(int i = 0; i < 150; ++i) { sth[i] = things(); rep[i].clear(); } for(int i = 1; i <= N; ++i) { scanf("%d%d%d", &P, &L, &X); sth[i] = things(i, P, L); for(int j = 1; j <= X; ++j) { scanf("%d%d", &Tt, &V); rep[i].push_back(things(Tt, V)); } } S = 0; T = 1; for(int i = 1; i <= N; ++i) { addedge(S, i, sth[i].p); for(int j = 0; j < rep[i].size(); ++j) { addedge(rep[i][j].n, i, rep[i][j].p); addedge(S, rep[i][j].n, sth[rep[i][j].n].p); } }}void getSSSP(int minM, int maxM){ memset(d, 0x3f, sizeof(d)); memset(vis, 0, sizeof(vis)); priority_queue
Q; d[S] = 0; Q.push(node(S, 0)); while(!Q.empty()) { node t = Q.top(); Q.pop(); vis[t.n] = true; for(int j = pnt[t.n]; j != nil; j = nxt[j]) { if((!vis[v[j]]) && (sth[v[j]].m >= minM) && (sth[v[j]].m <= maxM) && (d[v[j]] > t.dis + w[j])) { d[v[j]] = t.dis + w[j]; Q.push(node(v[j], d[v[j]])); } } }}void work(){ for(int i = sth[T].m - M; i <= sth[T].m; ++i) { getSSSP(i, i + M); ans = min(ans, d[T]); } printf("%d\n", ans);}int main(){ while(scanf("%d%d", &M, &N) == 2) { init(); work(); } return 0;}
  • 总结
    题见得多了,建图的感觉自然就有了。

转载地址:http://qgutl.baihongyu.com/

你可能感兴趣的文章