題目鏈接：

Modules

描述

? ? 蒜頭有一塊主板，為了提升其性能，可在主板上安置若干增強(qiáng)模塊。蒜頭有n個(gè)不同的增強(qiáng)模塊，增強(qiáng)模塊可以直接安置在主板上，也可以安置在已經(jīng)直接或間接連接在主板上的其他增強(qiáng)模塊上。

? ? 每個(gè)增強(qiáng)模塊具有一個(gè)初始強(qiáng)化值，其中第i個(gè)模塊的初始強(qiáng)化值為Pi。在所有模塊安置完成后，每個(gè)模塊的最終強(qiáng)化值為其自身初始強(qiáng)化值及直接安置在其上的所有模塊的最終強(qiáng)化值之和。

? ? 除此之外，有m對(duì)模塊由于具有良好的契合度，在安置時(shí)可以獲得額外的強(qiáng)化值加成：將模塊Aj直接安置在模塊Bj上時(shí)，模塊Bj的強(qiáng)化值可以獲得Qj的額外加成。

? ? 主板的最終強(qiáng)化值為直接安置在主板上的所有模塊最終強(qiáng)化值之和，請(qǐng)合理安置模塊使得主板獲得最大的強(qiáng)化值，并輸出最大強(qiáng)化值。

輸入

輸入第一行為一個(gè)整數(shù)T，表示一共有T組測(cè)試數(shù)據(jù)。

對(duì)于每組測(cè)試數(shù)據(jù)：

第一行為兩個(gè)整數(shù)n，m（1≤n≤3000，0≤m≤3000）。

第二行為n個(gè)整數(shù)Pi（1≤Pi≤109），數(shù)之間以單個(gè)空格間隔。

接下來m行中，第j行有三個(gè)整數(shù)Aj，Bj，Qj（1≤Aj,Bj≤n，Aj≠Bj，1≤Qj≤109）。

數(shù)據(jù)保證同一組（Aj，Bj）只出現(xiàn)一次。

輸出

對(duì)于每組測(cè)試數(shù)據(jù)：輸出一個(gè)整數(shù)表示主板的最大強(qiáng)化值。

樣例輸入1 1 3 4 1 2 4 3 1 8 3 2 16 2 1 32 1 2 64 樣例輸出1 87

題意:

思路：可以發(fā)現(xiàn)所有的p最后都會(huì)加到答案上,然后那些邊要求不能有環(huán)，而且出度為1，把邊方向就是求最大樹形圖了，可以建一個(gè)虛根，然后向每個(gè)點(diǎn)連邊，跑朱劉算法就好了，這里的最大樹形圖一定存在（加了根之后邊數(shù)會(huì)變多，我數(shù)組開小了一直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; }

　　

?

轉(zhuǎn)載于:https://www.cnblogs.com/zhangchengc919/p/6877991.html

總結(jié)

以上是生活随笔為你收集整理的Modules(最小树形图)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。