[항저우전다교 2020] 제2회 1001.Total Eclipse(및 조회)
14919 단어 함께 조사하여 모으다
제목 링크
아이디어:
권치에 따라 큰 것부터 작은 것까지 순서대로 정렬한 다음에 순서대로 가입하고 전체 장내의 권치를 현재의 권치로 줄인다.연결 블록의 총 개수를 수집하고 유지하면 된다.
코드:
#include
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N=1e5+7;
const int M=4e5+8;
const double eps=1e-8;
const int mod=1e9+7;
const int inf=0x7fffffff;
const double pi=3.1415926;
int a[N],h[N],e[M],ne[M],f[N],q[N],fa[N],idx;
bool visit[N];
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int find(int x)
{
if(x!=f[x])
{
f[x]=find(f[x]);
}
return f[x];
}
int cmp(int x,int y)
{
return a[x]>a[y];
}
signed main()
{
IOS;
int t;
cin>>t;
while(t--)
{
memset(h,-1,sizeof h);
memset(visit,0,sizeof visit);
memset(fa,0,sizeof fa);
int n,m;
cin>>n>>m;
idx=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
f[i]=q[i]=i;
}
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
sort(q+1,q+1+n,cmp);
for(int i=1;i<=n;i++)
{
int u=q[i];
visit[u]=1;
for(int j=h[u];~j;j=ne[j])
{
int k=e[j];
if(!visit[k])
{
continue;
}
int v=find(k);
if(v==u)
{
continue;
}
f[v]=fa[v]=u;
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
ans+=a[i]-a[fa[i]];
}
cout<<ans<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ 2236 Wireless Network 간편한 검색 및 수집
The ACM (Asia Cooperated Medical team) have set up a wireless network with the lap computers, but an unexpected aftersho...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N=1e5+7;
const int M=4e5+8;
const double eps=1e-8;
const int mod=1e9+7;
const int inf=0x7fffffff;
const double pi=3.1415926;
int a[N],h[N],e[M],ne[M],f[N],q[N],fa[N],idx;
bool visit[N];
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int find(int x)
{
if(x!=f[x])
{
f[x]=find(f[x]);
}
return f[x];
}
int cmp(int x,int y)
{
return a[x]>a[y];
}
signed main()
{
IOS;
int t;
cin>>t;
while(t--)
{
memset(h,-1,sizeof h);
memset(visit,0,sizeof visit);
memset(fa,0,sizeof fa);
int n,m;
cin>>n>>m;
idx=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
f[i]=q[i]=i;
}
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
sort(q+1,q+1+n,cmp);
for(int i=1;i<=n;i++)
{
int u=q[i];
visit[u]=1;
for(int j=h[u];~j;j=ne[j])
{
int k=e[j];
if(!visit[k])
{
continue;
}
int v=find(k);
if(v==u)
{
continue;
}
f[v]=fa[v]=u;
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
ans+=a[i]-a[fa[i]];
}
cout<<ans<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ 2236 Wireless Network 간편한 검색 및 수집The ACM (Asia Cooperated Medical team) have set up a wireless network with the lap computers, but an unexpected aftersho...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.