做了几道PKU上的图论，感觉PKU上的图论题很坑人。都是属于比较不易理解，且变化丰富的。这样也好，被虐多了，或许感觉就慢慢来了。3013，做了一两天了。表示累透了~~此题一上来第一反应就是图论，可是当我花了不少时间彻底理解了题目后，却发现有点儿不像图论，怪怪的，毛毛的，下面会解释。
题意：
某人过圣诞节，要买个圣诞树，然后正常的想要尽量花最小的钱达到要求。这个图是一棵倒着的树，每一条边都有单价，每个节点也由各自的重量，边与边的单价由于形状不一样，单价也不一样，其实就是做最短路的“权值”啦，但是这道题又有点儿BT，它算整棵树的价值不是权值相加。
重点：它是这样来算每条边的总价的。每条边的总价==（这条边的单价）X（以这条边的尾结点为根节点的那棵树的所有节点的重量之和）。还是很难理解？举个小例子：例如下面这个图中的边2-3，那么这条边2-3的总价值是它的（单价）X（节点5的重量+节点7的重量+节点6的重量+节点3的重量）。因为以3为根节点的树的所有节点为：5,7,6,3，嘛。。
然后这道题如何跟最短路扯上关系？题意已经理解清楚了，可是还是有毛毛的感觉。不知道从何入手。
解题思路：（以1-2表示节点1到节点2的边哦，5表示节点5的重量，以此类推）
动手画一画，发挥你的数学功底。想想哦，总价值的公式为：(1-2)X(2+4+3+5+6+7)+(2-4)X4+(2-3)X(3+5+6+7)+(3-5)X5+(3-7)X7+(3-6)X6。然后提取公因式，把相同边都提取出来，式子就变成了从节点1到每个节点的最短路径X该节点的重量。哈哈，是不是有想法了？
这样就能用一般的最短路处理了。
题的烦恼：
题超BT，说神马各个值<2^16次方，那么就表示，有可能用来存放dis[]的数组的值会超过int型而溢出，所以dis[]只能用__int64来存放，结果ans也要用__int64.好吧，这里让我郁闷了好久好久。还有就是主函数的输入用邻接表来存储的时候，我因为每个结构体的起始点弄错而纠结，唉，肿么最近老是变量看错啊。
代码：
| #include<iostream> using namespace std; const int MAXV=70001; const __int64 infinity=0xfffffffffffff;//最大值要用__int64 struct edge { int u; int v; int w; int next; }edge[MAXV*2]; int nv,ne; int arrHead[MAXV],queue[MAXV*2],val[MAXV]; __int64 dis[MAXV];//dis[]也得用__int64，int会溢出的 bool visited[MAXV]; void spfa(int s) { int i,head,top,u,v,w; for(i=1;i<=nv;i++) { dis[i]=infinity;//存每个点的最短路 visited[i]=0; } top=1,head=0; queue[top]=s; dis[s]=0; //SPFA的经典队列 while(head<top) { head=(head+1)%MAXV; u=queue[head]; visited[u]=0; for(i=arrHead[u];i!=-1;i=edge[i].next) { v=edge[i].v,w=edge[i].w; if(dis[v]>dis[u]+w) { dis[v]=dis[u]+w; if(!visited[v]) { top=(top+1)%MAXV; queue[top]=v; visited[v]=1; } } } } __int64 ans; //从节点1到每个节点的最短路X每个节点的重量的总和即为圣诞树的总价值 for(i=2,ans=0;i<=nv;i++) { if(dis[i]==infinity) { cout<<"No Answer"<<endl; break; } ans+=dis[i]*val[i]; } if(i>nv) cout<<ans<<endl; return ; } int main(void) { int cas,szEdge,s,e,w,i; scanf("%d",&cas); while(cas--) { scanf("%d%d",&nv,&ne);//节点，边 memset(arrHead,-1,sizeof(arrHead));//注意如果这里用for初始化的话，要考虑nv=0的情况 for(i=1;i<=nv;i++) scanf("%d",&val[i]);//节点的重量 szEdge=0; for(i=1;i<=ne;i++)//邻接表输入 { szEdge++; scanf("%d%d%d",&s,&e,&w);//边以及边的单价 edge[szEdge].u=s; edge[szEdge].v=e; edge[szEdge].w=w; edge[szEdge].next=arrHead[s]; arrHead[s]=szEdge; szEdge++; edge[szEdge].u=e; edge[szEdge].v=s; edge[szEdge].w=w; edge[szEdge].next=arrHead[e]; arrHead[e]=szEdge; } spfa(1); } return 0; } |