Modules(最小树形图)

题目链接：

Modules

描述

蒜头有一块主板，为了提升其性能，可在主板上安置若干增强模块。蒜头有n个不同的增强模块，增强模块可以直接安置在主板上，也可以安置在已经直接或间接连接在主板上的其他增强模块上。

每个增强模块具有一个初始强化值，其中第i个模块的初始强化值为Pi。在所有模块安置完成后，每个模块的最终强化值为其自身初始强化值及直接安置在其上的所有模块的最终强化值之和。

除此之外，有m对模块由于具有良好的契合度，在安置时可以获得额外的强化值加成：将模块Aj直接安置在模块Bj上时，模块Bj的强化值可以获得Qj的额外加成。

主板的最终强化值为直接安置在主板上的所有模块最终强化值之和，请合理安置模块使得主板获得最大的强化值，并输出最大强化值。

输入

输入第一行为一个整数T，表示一共有T组测试数据。

对于每组测试数据：

第一行为两个整数n，m（1≤n≤3000，0≤m≤3000）。

第二行为n个整数Pi（1≤Pi≤109），数之间以单个空格间隔。

接下来m行中，第j行有三个整数Aj，Bj，Qj（1≤Aj,Bj≤n，Aj≠Bj，1≤Qj≤109）。

数据保证同一组（Aj，Bj）只出现一次。

输出

对于每组测试数据：输出一个整数表示主板的最大强化值。

样例输入1

样例输出1

87

题意:

思路：可以发现所有的p最后都会加到答案上,然后那些边要求不能有环，而且出度为1，把边方向就是求最大树形图了，可以建一个虚根，然后向每个点连边，跑朱刘算法就好了，这里的最大树形图一定存在（加了根之后边数会变多，我数组开小了一直wa）
AC代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn=3e3+10;

LL ans=0;

const LL inf=1e14;

int n,m,vis[maxn],id[maxn],pre[maxn],cnt=0;

LL in[maxn];

struct Edge

{

    int u,v;

    LL cost;

}edge[2*maxn];

inline void add_edge(int u,int v,LL w)

{

    cnt++;

    edge[cnt].u=u;

    edge[cnt].v=v;

    edge[cnt].cost=w;

}

inline LL solve()

{

    LL ret=0;

    int root=0;

    for(int i=1;i<=n;i++)add_edge(root,i,0);

    n=n+1;

    while(true)

    {

        for(int i=0;i<n;i++)in[i]=-inf;

        for(int i=1;i<=cnt;i++)

        {

            if(edge[i].cost>in[edge[i].v]&&edge[i].u!=edge[i].v)

            {

                in[edge[i].v]=edge[i].cost;

                pre[edge[i].v]=edge[i].u;

            }

        }

        int cntnode=0;

        memset(id,-1,sizeof(id));

        memset(vis,-1,sizeof(vis));

        in[root]=0;

        for(int i=0;i<n;i++)

        {

            ret=ret+in[i];

            int v=i;

            while(vis[v]!=i&&v!=root&&id[v]==-1)

            {

                vis[v]=i;

                v=pre[v];

            }

            if(id[v]==-1&&v!=root)

            {

                for(int u=pre[v];u!=v;u=pre[u])id[u]=cntnode;

                id[v]=cntnode++;

            }

        }

        if(cntnode==0)break;

        for(int i=0;i<n;i++)

        {

            if(id[i]==-1)id[i]=cntnode++;

        }

        for(int i=1;i<=cnt;i++)

        {

            int v=edge[i].v;

            edge[i].u=id[edge[i].u];

            edge[i].v=id[edge[i].v];

            if(edge[i].u!=edge[i].v)

            {

                edge[i].cost-=in[v];

            }

        }

        n=cntnode;

       root=id[root];

    }

    return ret;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        cnt=0;ans=0;

        int u,v,w,x;

        for(int i=1;i<=n;i++)scanf("%d",&x),ans=ans+x;

        for(int i=1;i<=m;i++)

        {

            scanf("%d%d%d",&u,&v,&w);

            add_edge(v,u,(LL)w);

        }

        printf("%lld\n",solve()+ans);

    }

    return 0;

}

bj

Modules(最小树形图)

Modules