poj-3013-Big Christmas Tree

妖狐艹你老母 2022-05-19 00:37 130阅读 0赞

Big Christmas Tree

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;3000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;131072K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;26375</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;5723</td> 
  </tr> 
 </tbody> 
</table>

Description

Christmas is coming to KCM city. Suby the loyal civilian in KCM city is preparing a big neat Christmas tree. The simple structure of the tree is shown in right picture.

The tree can be represented as a collection of numbered nodes and some edges. The nodes are numbered 1 through *n*. The ![3013_1.gif][]root is always numbered 1. Every node in the tree has its weight. The weights can be different from each other. Also the shape of every available edge between two nodes is different, so the unit price of each edge is different. Because of a technical difficulty, price of an edge will be (sum of weights of all descendant nodes) × (unit price of the edge).

Suby wants to minimize the cost of whole tree among all possible choices. Also he wants to use all nodes because he wants a large tree. So he decided to ask you for helping solve this task by find the minimum cost.

Input

The input consists of *T* test cases. The number of test cases *T* is given in the first line of the input file. Each test case consists of several lines. Two numbers *v*, *e* (0 ≤ *v*, *e* ≤ 50000) are given in the first line of each test case. On the next line, *v* positive integers *wi* indicating the weights of *v* nodes are given in one line. On the following *e* lines, each line contain three positive integers *a*, *b*, *c* indicating the edge which is able to connect two nodes *a* and *b*, and unit price *c*.

All numbers in input are less than 216.

Output

For each test case, output an integer indicating the minimum possible cost for the tree in one line. If there is no way to build a Christmas tree, print “No Answer” in one line.

Sample Input

2
    2 1
    1 1
    1 2 15
    7 7
    200 10 20 30 40 50 60
    1 2 1
    2 3 3
    2 4 2
    3 5 4
    3 7 2
    3 6 3
    1 5 9

Sample Output

15
    1210

Source

[POJ Monthly--2006.09.29][], Kim, Chan Min (kcm1700@POJ)

题目大意：让你做一棵圣诞树，这棵树要最大，而且花费还要最小，所以想到可以用最短路来做，题目中花费标准为每个点到到其根节点的路径\*权重，反正就是大概这个意思，中文题意在[哈理工1419][1419]；

思路：对于题中第二个样例我的理解：

由于1为根节点，1上连2（1与5去掉），2上连4和3，3上连5 6 7，所以5 6 7到3的价钱为40\*4+60\*2+50\*3

3到2的价钱为（20+30+50+60）\*3，4到2价钱为30\*2，然后2到1的价钱为：（10+20+30+40+50+60）∗1

所以总价钱=40∗4+60∗2+50∗3+（40+60+50+20）∗3+30∗2+（10+20+30+40+50+60）∗1

=40\*8+60\*6+50\*7+20\*4+30\*3+10=1210

=每个点到根节点的距离\*权重

可以看出刚好是每个点到根节点的距离\*权重，

然后用spfa算法求出即可，再判断能不能构成完整的图；

代码：

#include<map>
    #include<stack>
    #include<cmath>
    #include<queue>
    #include<string>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    using namespace std;
    #define maxn 50005
    #define INF 0x3f3f3f3f3f
    #define ll long long
    int val[maxn];
    int first[maxn];
    ll dis[maxn];
    int book[maxn];
    int n,m;
    int cnt;
    struct qq
    {
        int v,w,next;
    } a[maxn*2];
    void bulid(int u,int v,int w)
    {
        a[cnt].v=v;
        a[cnt].w=w;
        a[cnt].next=first[u];
        first[u]=cnt++;
    }
    void spfa(int x)
    {
        int i,j;
        memset(book,0,sizeof(book));
        for(i=1; i<=n; i++)
            dis[i]=INF;
        book[x]=1;
        dis[x]=0;
        queue<int>Q;
        Q.push(x);
        while(!Q.empty())
        {
            x=Q.front();
            Q.pop();
            book[x]=0;
            for(i=first[x]; i!=-1; i=a[i].next)
            {
                int vv=a[i].v;
                int ww=a[i].w;
                if(dis[vv]>dis[x]+ww)
                {
                    dis[vv]=dis[x]+ww;
                    if(!book[vv])
                    {
                        book[vv]=1;
                        Q.push(vv);
                    }
                }
            }
        }
    }
    int main()
    {
        int test;
        scanf("%d",&test);
        while(test--)
        {
            int i,j;
    
            cnt=1;
            memset(first,-1,sizeof(first));
            scanf("%d%d",&n,&m);
            for(i=1; i<=n; i++)
                scanf("%d",&val[i]);
                int u,v,w,flag=0;
            for(i=1; i<=m; i++)
            {
                scanf("%d%d%d",&u,&v,&w);
                bulid(u,v,w);
                bulid(v,u,w);
            }
            ll ans=0;
            spfa(1);
            for(i=2; i<=n; i++)
            {
                if(dis[i]==INF)
                {
                    flag=1;
                    break;
                }
                ans+=dis[i]*val[i];
            }
            if(flag)
                printf("No Answer\n");
            else
                printf("%lld\n",ans);
        }
        return 0;
    }

[3013_1.gif]: /images/20220519/22f38851676742e3947128dfba4ff648.png
[POJ Monthly--2006.09.29]: http://poj.org/searchproblem?field=source&key=POJ+Monthly--2006.09.29
[1419]: http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1419