Hrbust 2222 应援团补完计划【并查集+思维】好题~

应援团补完计划

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 迅速出道的重要条件是足够的应援团人气，可是经理人Wangzhpp并不清楚如何才能最大化应援团的人气，只能求助于你。 应援团中有n个团员，m个友谊关系，第i个友谊关系的强度为w[i]，因此，我们可以将团员及其关系抽象为一个有n个点、m条边的无向图（允许重边，不保证图联通）。 我们可以将每个联通块视为应援团内的一个小队，人数为i的小队所能提供的人气值为a[i]。 为了保证xiaodao的人气最大化，经理人决定”只保留强度在区间[l,r]内的友谊关系。”，也就是说只有边权不在[l,r]内的边统统会被拆毁。 而我们所需要做的，就是找到所能提供的最大人气！

Input

第一行一个整数 T ，代表有 T 组数据。 每组数据 第一行两个整数 N(<=1000) , M(<=5000) 代表有 N 个人 M 个关系。 第二行N个整数，第i个整数a[i]代表有i个人的小队所能提供的人气。 接下来M行，每行三个整数u[i],v[i],w[i]，代表u[i]与v[i]之间有着强度为w[i]的关系。

Output

对于每组数据输出一个整数，代表最大的人气値。

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程序设计团队赛

思路：

首先我们按照边权从小到大排序。

接下来暴力O（m^2）去枚举一个区间的起点和终点，然后在枚举的过程中，维护一个值sum，表示合并到当前情况的总价值。

那么每一次更新的时候，我们都要对sum进行动态更新：

sum需要减去当前边的两个端点所在集合的大小所贡献的值。

sum需要加上当前边的两个端点合并之后所在集合的大小所贡献的值。

那么当然，如果两个端点已经在一个集合中，那么就不能进行上述操作了。

过程维护最大值。

这个题好在想到做法之后可能会忘记一个坑，题目要求的是，对于权值处于区间【l，r】内的全部边保留，此外的全部拆除。

所以我们在过程维护最终解的时候，要注意是否还存在与起点和终点权值相等的边存在。

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);    }}