题目大意:
一开始想用并查集,发现很难维护联通块的代表元素,所以用了宽搜,开数组会炸,所以开一个优先队列维护,每扫完一个联通块,统计答案,清空优先队列,!!千万记住注意数组的大小!!!
代码:
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<queue>
#define int long long
#define N 1005000
using namespace std;
int n,m,l,val[N],head[N],cnt,tot,ans;
int siz[N];
bool vis[N];
struct node{int to,nxt;}e[N];
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘){x=x*10 ch-‘0‘;ch=getchar();}
return x*f;
}
void add(int from,int to)
{
e[ cnt] = (node){to,head[from]};
head[from]=cnt;
}
queue<int> q;
priority_queue <int> dij;
void bfs(int x)
{
vis[x]=1;
int siz=0;
siz =(val[x]-1);
ans =x;
dij.push(x);
q.push(x);
while(!q.empty())
{
int s=q.front();
q.pop();
for(int i=head[s];i;i=e[i].nxt)
{
int y=e[i].to;
if(!vis[y]){
vis[y]=1;
q.push(y);
siz =(val[y]-1);
dij.push(y);
ans =y;
}
}
}
while(siz){
int xx=dij.top(); dij.pop();
if(siz<=l-1)
{
ans =siz*xx;
siz=0;
}
if(siz>(l-1))
{
siz-=(l-1);
ans =xx*(l-1);
}
}
while(dij.size()) dij.pop();
}
signed main()
{
#ifdef yilnr
#else
freopen("pmlaw.in","r",stdin);
freopen("pmlaw.out","w",stdout);
#endif
n=read();m=read();l=read();
for(int i=1;i<=n;i )val[i]=read();
for(int i=1,x,y;i<=m;i )
{
scanf("%lld%lld",&x,&y);
add(x,y);add(y,x);
}
for(int i=1;i<=n;i )if(!vis[i])bfs(i);
printf("%lldn",ans);
fclose(stdin);fclose(stdout);
return 0;
}