POJ 3013 Big Christmas Tree

图论，最短路(变形)

传送门：POJ

---

题意

给n个点从1到n标号，下面一行是每个点的权，另外给出m条边，下面是每条边的信息，两个端点和边的权值，边是无向边。你的任务是选出一些边，使这个图变成一棵树，且花费最小。这棵树的花费是这样算的，1号固定为树根，树中每个节点下面的边都有个边权，然后边权乘上这条边的下面所有的子孙后代的点权和。（看sample2，只要除掉边 1 5 9 按照这个方法就能算出1210）

---

思路

很像最小生成树，仔细研究，没法这样做。因为每条边在找到这颗树之前很难计算它的价值。本来你算好的边的价值，但是在去掉某些边时，会导致边的价值发生变化。

推公式，发现树的价值等于点权乘以点到根节点的最短路的边权和。转化为找单源最短路。

值得注意的是这题有坑：

不能邻接表建图，卡vector。链式前向星吧。

edge数组开2倍，因为边是双向的，两条。链式前向行星的head也注意一下。

Dij和spfa都能过。

n=0或者1， 答案是0，而不是no answer。并且也要将数据读入，不能直接输出0就不管输入了，否则会re。

数据范围大，要用long long，注意强制转型。

---

代码

细节挺多，多加注意吧

#include <iostream> #include <cstdio> #include <algorithm> #include <cstdlib> #include <cstring> #include <cmath> #include <vector> #include <queue> #include <stack> #include <iomanip> #include <string> #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; const int MAXN=100005; typedef long long LL; const LL loo=4500000000000000000ll; struct Edge{ int from; int to; int cost; int next; }; Edge edge[MAXN];//储存边 int cost[MAXN]; int head[MAXN]; LL d[MAXN];//d[i]表示源点s到点i的最短路 bool vis[MAXN];//vis[i]=1表示点i在队列中 vis[i]=0表示不在队列中 void spfa(int n,int s)//源点s { queue <int> q; memset(d,0x3f,sizeof(d)); d[s]=0; memset(vis,0,sizeof(vis)); q.push(s); vis[s]=1; //顶点入队vis要做标记 while(!q.empty()) { int x; x=q.front(); q.pop(); vis[x]=0; //队头元素出队，并且消除标记 for(int k=head[x]; k!=-1; k=edge[k].next)//遍历顶点x的邻接表 { int y=edge[k].to; if(d[x]+(LL) edge[k].cost < d[y]) { d[y]=d[x]+(LL) edge[k].cost;//松弛 if(!vis[y])//顶点y不在队内 { vis[y]=1;//标记 q.push(y);//入队 } } } } } void add(int u,int v,int w,int k) { edge[k].from=u; edge[k].to=v; edge[k].cost=w; edge[k].next=head[u]; head[u]=k++; edge[k].from=v; edge[k].to=u; edge[k].cost=w; edge[k].next=head[v]; head[v]=k++; } int main(void) { int T; scanf("%d",&T); while(T--) { int m,n; scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); memset(edge,0,sizeof(edge)); for(int i=1;i<=n;i++) { scanf("%d",&cost[i]); } for(int i=1;i<=2*m;i+=2) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c,i); } if(n>0) spfa(n,1); LL res=0; int flag=0; for(int i=1;i<=n;i++) { if(d[i]>loo) { flag=1; break; } res+=((LL) cost[i]*d[i]); } if(!flag) printf("%I64d\n",res); else printf("No Answer\n"); } return 0; }