hdu3696Farm Game(SPFA求最长说)
hdu3696Farm Game(SPFA求最长路)
题目请戳这里
题目大意:有n种物品,每种有相应的价值和数量。现在给m组关系链,组成一张关系网,表示某物品之间相互转换的关系。求已知的物品能获得的最大价值。
题目分析:每种物品可以直接卖掉,也可以通过转换成价值更高的物品再卖以获取更高的价值。对每个物品的单价建图,求每个物品通过转化所能获得的最大单价,然后再卖掉,可以获得最大价值。设一个源点s,s到每个物品建边,边权log10(p[i]),为相应物品的单价取对数(乘法转化成加法),表示不通过任何交换各个物品的价值。然后对于能够交换的物品(i,j),设单位i可以得到bi的j,j->i建边,边权log10(bi),表面通过j,可以使i的价值发生变化。然后从s跑一遍最长路,最后每种物品的单价*数量便是最大的价值。
详情请见代码:
#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N = 10005; const int M = 25005; typedef __int64 ll; int head[N]; struct node { double val; int to,next; }g[M<<3]; int n,m,num; int que[N]; bool in[N]; int times[N]; double dis[N]; double ans; double p[N],w[N]; void build(int s,int e,double v) { g[num].to = e; g[num].val = v; g[num].next = head[s]; head[s] = num ++; } void SPFA() { int i,front,rear; for(i = 0;i <= n;i ++) { dis[i] = 0; in[i] = false; times[i] = 0; } front = rear = 0; dis[0] = 0; que[rear ++] = 0; in[0] = true; times[0] ++; while(front != rear) { int u = que[front ++]; if(front == N) front = 0; in[u] = false; for(i = head[u];~i;i = g[i].next) if(dis[g[i].to] < dis[u] + g[i].val) { dis[g[i].to] = dis[u] + g[i].val; if(in[g[i].to] == false)// && times[g[i].to] < n) { in[g[i].to] = true; times[g[i].to] ++; que[rear ++] = g[i].to; if(rear == N) rear = 0; } } } } void solve() { SPFA(); for(int i = 1;i <= n;i ++) { if(p[i] < pow(10.0,dis[i])) p[i] = pow(10.0,dis[i]); ans += p[i] * w[i]; } printf("%.2lf\n",ans); } int main() { int i,k,a,b; while(scanf("%d",&n),n) { ans = 0; memset(head,-1,sizeof(head)); num = 0; for(i = 1;i <= n;i ++) { scanf("%lf%lf",&p[i],&w[i]); build(0,i,log10(p[i])); } scanf("%d",&m); while(m --) { scanf("%d",&k); scanf("%d",&a); k --; double pp; while(k --) { scanf("%lf%d",&pp,&b); build(b,a,log10(pp)); a = b; } } solve(); } return 0; }