codevs1955光纤通信(并查集)

时间:2021-05-24 10:27:46
/*
第一眼以为就是个区间覆盖
然后敲完提交60分0.0 然而觉得自己的做法很对
以为数据错了 后来发现XXX他的牛棚是一圈(牛过得挺好的啊 还能赏湖...)
然后枚举断开的点 可惜n=750 p=10000 这组数据TLE了 1.3秒的样子 90分
后来看题解说可以并查集 觉得好有道理的样子 0.0
下面是两次的代码
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 10010
using namespace std;
struct node
{
int l,r;
}boy[maxn];
int cmp(const node &x,const node &y)
{
if(x.l==y.l)return x.r<y.r;
return x.l<y.l;
}
int n,p,k,ans,minn=;
int main()
{
scanf("%d%d",&n,&p);
int x,y;
for(int i=;i<=p;i++)
{
scanf("%d%d",&x,&y);
boy[i].l=x;boy[i].r=y;
}
for(k=;k<=n;k++)
{
ans=;
for(int i=;i<=p;i++)
{
if(boy[i].l<k)boy[i].l+=n;
if(boy[i].r<k)boy[i].r+=n;
if(boy[i].l>boy[i].r)swap(boy[i].l,boy[i].r);
}
sort(boy+,boy++p,cmp);
int ri=boy[].r,li=boy[].l;
for(int i=;i<=p;i++)
if(boy[i].l>ri)
{
ans=ans+ri-li;
li=boy[i].l;
ri=boy[i].r;
}
else ri=max(ri,boy[i].r);
ans=ans+ri-li;
minn=min(minn,ans);
}
printf("%d",minn);
return ;
}
/*
并查集
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 10010
using namespace std;
int fa[maxn],l[maxn],r[maxn],n,p,ans,Ans=;
int find(int x)
{
if(x!=fa[x])fa[x]=find(fa[x]);
return fa[x];
}
void unionn(int x,int y)
{
if(x>y)swap(x,y);
for(int i=x;i<y;i++)
if(find(i)!=find(i+))
{
ans++;
fa[find(i)]=find(i+);
}
}
int main()
{
cin>>n>>p;
for(int i=;i<=p;i++)
cin>>l[i]>>r[i];
for(int k=;k<=n;k++)
{
ans=;
for(int i=;i<=n*;i++)fa[i]=i;
for(int i=;i<=p;i++)
{
int tmp1=l[i],tmp2=r[i];
if(tmp1<k)tmp1=tmp1+n;
if(tmp2<k)tmp2=tmp2+n;
if(find(tmp1)!=find(tmp2))unionn(find(tmp1),find(tmp2));
}
Ans=min(Ans,ans);
}
cout<<Ans;
return ;
}