首页 > 代码库 > 【kruscal】【最小生成树】【离线】洛谷 P2266 爱的距离
【kruscal】【最小生成树】【离线】洛谷 P2266 爱的距离
建图：每个点向它四周的点连边权为两点点权的差的绝对值的边。
由于有多个需要“施法”的点，所以相当于对每个这样的点，询问与它的距离在T以内的最长边的最小值，即多次询问。
最长边最小之类的，肯定是最小生成树没跑了。BUT 若是对每个点这样做的话，肯定会TLE。
所以考虑一次处理出所有询问的答案。
在并查集将两个点集连边的时候，若两个点集的点数和<T，则对这两个集内的询问点都没有影响。
若两个点集的点数和>=T，则若A(B)集原来的点数<T，则A(B)集内的询问点都符合了题意，这个最大值就是当前这条边的边权，当然kruscal是贪心的，所以这个值是最小的。
所以并查集除了维护连通性之外，还要维护某个集合的顶点数以及某个集合的询问点数。
P.S.由于NOIP用**的devc++4.9.9.2，所以手贱地试了试，太**了，没有括号匹配，并且调试和缩进和热键都很猥琐。
P.S.P.S.运行时界面没有停留，要最后加上for(;;);，提交前千万别忘了删掉！！！！！！否则TLE得死不瞑目(<---怒立flag)。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 #define N 601 5 typedef long long ll; 6 int Abs(const int &x){return x<0 ? (-x) : x;} 7 struct Edge 8 { 9 int u,v,w;10 Edge(const int &a,const int &b,const int &c){u=a;v=b;w=c;}11 Edge(){}12 }edges[(N*N)<<2];13 bool operator < (const Edge &a,const Edge &b){return a.w<b.w;}14 int n,m,K,fa[N*N],rank[N*N],a[N][N],nm,num[N][N],en,cnt[N*N],tot,ask_sum[N*N];15 bool b[N*N];16 ll ans;17 void init(){for(int i=1;i<=nm;i++) fa[i]=i,cnt[i]=1,ask_sum[i]=b[i];}18 int findroot(int x)19 {20 if(x==fa[x]) return x;21 int rt=findroot(fa[x]);22 fa[x]=rt;23 return rt;24 }25 void Union(const int &U,const int &V)26 {27 if(rank[U]<rank[V]) fa[U]=V,cnt[V]+=cnt[U],ask_sum[V]+=ask_sum[U];28 else29 {30 fa[V]=U; cnt[U]+=cnt[V]; ask_sum[U]+=ask_sum[V];31 if(rank[U]==rank[V]) rank[U]++;32 }33 }34 int main()35 {36 scanf("%d%d%d",&n,&m,&K); nm=n*m;37 for(int i=1;i<=n;i++)38 for(int j=1;j<=m;j++)39 {40 scanf("%d",&a[i][j]);41 num[i][j]=++en;42 } en=0;43 for(int i=1;i<=n;i++)44 for(int j=1;j<=m;j++)45 scanf("%d",&b[num[i][j]]);46 for(int i=1;i<=n;i++)47 for(int j=1;j<=m;j++)48 {49 if(i!=n) edges[++en]=Edge(num[i][j],num[i+1][j],Abs(a[i][j]-a[i+1][j]));50 if(j!=m) edges[++en]=Edge(num[i][j],num[i][j+1],Abs(a[i][j]-a[i][j+1]));51 }52 sort(edges+1,edges+en+1); init();53 for(int i=1;i<=en;i++)54 {55 int f1=findroot(edges[i].u),f2=findroot(edges[i].v);56 if(f1!=f2)57 {58 if(cnt[f1]+cnt[f2]>=K)59 {60 if(cnt[f1]<K) ans+=((ll)edges[i].w*(ll)ask_sum[f1]);61 if(cnt[f2]<K) ans+=((ll)edges[i].w*(ll)ask_sum[f2]);62 }63 Union(f1,f2); tot++;64 if(tot==nm-1) break;65 }66 }67 printf("%I64d\n",ans);68 return 0;69 }
【kruscal】【最小生成树】【离线】洛谷 P2266 爱的距离
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。