文章
25
粉丝
0
获赞
27
访问
1.4k
#include <bits/stdc++.h>
using namespace std;
const int maxn=1005;
#define INF 0x3f3f3f3f
int fa[maxn];
int find(int x){
if(fa[x]==x) return x;
fa[x]=find(fa[x]);
return fa[x];
}
struct node{
int no;//序号
int x1,y1,x2,y2,w;
};
vector<node> nodes;
//每次创建一个新区域,检查跟之前区域的联通情况,加入并查集
void newArea(int x1,int y1,int x2,int y2,int w){
nodes.push_back(node{nodes.size()+1,x1,y1,x2,y2,w});
fa[nodes.size()]=nodes.size();
for(node n:nodes){
if (n.no==nodes.size())
continue;
bool flag=true;//是否重叠
if(x1>n.x2||x2<n.x1||y1>n.y2||y2<n.y1)
flag=false;
if(flag){
//先找到两个集合的根节点,然后合并两个集合
fa[find(nodes.size())]=find(n.no);
}
}
}
//计算资源总量
//传入并查集根节点序号
int getResourceNum(int r){
int sum=0;
for(int i=1;i<=nodes.size();i++){
if(find(i)==r)
sum+=nodes[i-1].w;
}
return sum;
}
int...
登录后发布评论
暂无评论,来抢沙发