POJ 3013 - SPFA..为毛通过率这么低...

POJ 3013 - SPFA..为毛通过率这么低...

题意抽象来说..就是给一个无向图...要我们以结点1为根做一棵树...使得代价最小...代价的定义是说每条边乘以这条边下面的子树所有点之和...

令pointi指为i点的权值...Li为线段的权值

也就是说最后要求的是L1*(point2+point3+point..)+L2*(point2+point3+point..)+....这种式子的值最小...把这个式子化一下..可变成

point2(L1+L2+...)+point3(L1+L2...)....

为点的权值一开始就是确定的...所以题目就转化成了求每个点到点1的距离之和要最小...

因为题目是给的无向边...所以构边的时候要构一个正向一个反向...然后用Dijkstra 或者SPFA或者Bellman-Ford来求所有点到点1的最短路径...然后再将每个d[ ] 乘以该点的权值再都加起来就是答案所求的最小代价..

用Dijkstra效率低...必须要加Heap来优化才能在3000ms内过....Bellman-Ford也是效率低...而最好的方案还是SPFA...

注意的是....题目虽然所给的输入数据是不大于65536的...但最后的结果会很大...最好用 unsigned long long 来存储...读入和输出用 %I64u..

并且要注意判断"No Answer"的情况..

Program:

#include#include#define MAXN 50010using namespace std;struct pp{ int x,y,k,next; }line[MAXN*2];int n,m,i,T,link[MAXN];unsigned long long w[MAXN],d[MAXN];queue myqueue;void SPFA(){ int i,h,k; unsigned long long ans=0; bool used[MAXN],can[MAXN]; memset(d,0x7F,sizeof(d)); memset(can,false,sizeof(can)); memset(used,false,sizeof(used)); while (!myqueue.empty()) myqueue.pop(); d[1]=0; myqueue.push(1); while (!myqueue.empty()) { h=myqueue.front(); myqueue.pop(); used[h]=false; can[h]=true; k=link[h]; while (k) { if (d[line[k].y]>d[h]+line[k].k) { d[line[k].y]=d[h]+line[k].k; if (!used[line[k].y]) { myqueue.push(line[k].y); used[line[k].y]=true; } } k=line[k].next; } } for (i=1;i<=n;i++) if (!can[i]) { printf("No Answer\n"); return; } for (i=2;i<=n;i++) ans+=d[i]*w[i]; printf("%I64u\n",ans); }int main(){ scanf("%d",&T); while (T--) { memset(link,0,sizeof(link)); scanf("%d%d",&n,&m); for (i=1;i<=n;i++) scanf("%I64u",&w[i]); i=m; m=0; while (i--) { m++; scanf("%d%d%d",&line[m].x,&line[m].y,&line[m].k); line[m].next=link[line[m].x]; link[line[m].x]=m; m++; line[m].x=line[m-1].y; line[m].y=line[m-1].x; line[m].k=line[m-1].k; line[m].next=link[line[m].x]; link[line[m].x]=m; } SPFA(); } return 0; }

这里面pointi指的是i点的权值...Li值得是线段的权值

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。