應(yīng)援團補完計劃

Time Limit: 3000 MS Memory Limit: 32768 K Total Submit: 9(5 users) Total Accepted: 3(3 users) Rating:  Special Judge: No

Description

“因為生源驟減，心愛的ACM面臨廢部危機，為了保護所愛的一切，我所能做的，就是——成為偶像！” by xiaodao 迅速出道的重要條件是足夠的應(yīng)援團人氣，可是經(jīng)理人Wangzhpp并不清楚如何才能最大化應(yīng)援團的人氣，只能求助于你。 應(yīng)援團中有n個團員，m個友誼關(guān)系，第i個友誼關(guān)系的強度為w[i]，因此，我們可以將團員及其關(guān)系抽象為一個有n個點、m條邊的無向圖（允許重邊，不保證圖聯(lián)通）。 我們可以將每個聯(lián)通塊視為應(yīng)援團內(nèi)的一個小隊，人數(shù)為i的小隊所能提供的人氣值為a[i]。 為了保證xiaodao的人氣最大化，經(jīng)理人決定”只保留強度在區(qū)間[l,r]內(nèi)的友誼關(guān)系。”，也就是說只有邊權(quán)不在[l,r]內(nèi)的邊統(tǒng)統(tǒng)會被拆毀。 而我們所需要做的，就是找到所能提供的最大人氣！

Input

第一行一個整數(shù) T ，代表有 T 組數(shù)據(jù)。 每組數(shù)據(jù) 第一行兩個整數(shù) N(<=1000) , M(<=5000) 代表有 N 個人 M 個關(guān)系。 第二行N個整數(shù)，第i個整數(shù)a[i]代表有i個人的小隊所能提供的人氣。 接下來M行，每行三個整數(shù)u[i],v[i],w[i]，代表u[i]與v[i]之間有著強度為w[i]的關(guān)系。

Output

對于每組數(shù)據(jù)輸出一個整數(shù)，代表最大的人氣値。

Sample Input

2 4 4 1 50 2 9 1 2 6 2 3 8 3 4 4 1 4 3 4 4 1 5 2 9 1 2 6 2 3 8 3 4 4 1 4 3

Sample Output

100 10

Source

"誠德軟件杯"哈爾濱理工大學第四屆ACM程序設(shè)計團隊賽

思路：

首先我們按照邊權(quán)從小到大排序。

接下來暴力O（m^2）去枚舉一個區(qū)間的起點和終點，然后在枚舉的過程中，維護一個值sum，表示合并到當前情況的總價值。

那么每一次更新的時候，我們都要對sum進行動態(tài)更新：

sum需要減去當前邊的兩個端點所在集合的大小所貢獻的值。

sum需要加上當前邊的兩個端點合并之后所在集合的大小所貢獻的值。

那么當然，如果兩個端點已經(jīng)在一個集合中，那么就不能進行上述操作了。

過程維護最大值。

這個題好在想到做法之后可能會忘記一個坑，題目要求的是，對于權(quán)值處于區(qū)間【l，r】內(nèi)的全部邊保留，此外的全部拆除。

所以我們在過程維護最終解的時候，要注意是否還存在與起點和終點權(quán)值相等的邊存在。

Ac代碼：

#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;struct node{    int x,y,w;}a[50550];int jihe[10500];int f[10500];int val[10500];int cmp(node a,node b){    return a.w<b.w;}int find(int a){    int r=a;    while(f[r]!=r)    r=f[r];    int i=a;    int j;    while(i!=r)    {        j=f[i];        f[i]=r;        i=j;    }    return r;}int merge(int a,int b){    int A,B;    A=find(a);    B=find(b);    if(A!=B)    {        f[B]=A;        jihe[A]+=jihe[B];    }}int main(){    int t;    scanf("%d",&t);    while(t--)    {        int n,m;        scanf("%d%d",&n,&m);        for(int i=1;i<=n;i++)scanf("%d",&val[i]);        for(int i=0;i<m;i++)        {            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);        }        int output=val[1]*n;        sort(a,a+m,cmp);        for(int i=0;i<m;i++)        {            if(a[i].w==a[i-1].w)continue;            int sum=val[1]*n;            for(int j=1;j<=n;j++)f[j]=j,jihe[j]=1;            for(int j=i;j<m;j++)            {                if(find(a[j].x)!=find(a[j].y))                {                    sum-=val[jihe[find(a[j].x)]];                    sum-=val[jihe[find(a[j].y)]];                    merge(a[j].x,a[j].y);                    sum+=val[jihe[find(a[j].x)]];                }                if(a[j].w!=a[j+1].w)output=max(output,sum);            }        }        PRintf("%d/n",output);    }}