大屏网页设计网站,邯郸网站制作地方,58同城网站建设的不足,做软件开发的网站有哪些正题 题目大意
一条边的价格为两个点的曼哈顿距离乘B#xff0c;修建源点价格为A。要求每个联通块内都有源点的最小价格。 解题思路
对于最终每个联通块肯定是棵树。对于合并每个联通块可以减少一个源点。所以将最小生成树上价格小于A的边都加进去就可以了。 codecodecode
…正题 题目大意
一条边的价格为两个点的曼哈顿距离乘B修建源点价格为A。要求每个联通块内都有源点的最小价格。 解题思路
对于最终每个联通块肯定是棵树。对于合并每个联通块可以减少一个源点。所以将最小生成树上价格小于A的边都加进去就可以了。 codecodecode
#includecstdio
#includealgorithm
#define N 1010
using namespace std;
int n,A,B,x[N],y[N],ans,father[N],k,cnt,now;
struct node{int x,y,w;
}a[N*N];
int find(int x)
{if(father[x]x) return x;return find(father[x]);
}
void unionn(int x,int y)
{int fafind(x),fbfind(y);if(fafb) father[fa]fb;else father[fb]fa;
}
bool cmp(node x,node y)
{return x.wy.w;}
int main()
{freopen(pupil.in,r,stdin);freopen(pupil.out,w,stdout);scanf(%d%d%d,n,A,B);for(int i1;in;i)scanf(%d%d,x[i],y[i]);for(int i1;in;i)father[i]i;kn;for(int i1;in;i)for(int ji1;jn;j)a[cnt](node){i,j,abs(x[i]-x[j])abs(y[i]-y[j])};sort(a1,a1cnt,cmp);ans2147483647;for(int i1;icnt;i){if(a[i].w*BA) break;if(find(a[i].x)!find(a[i].y)){k--;unionn(a[i].x,a[i].y);nowa[i].w*B;}}printf(%d,k*Anow);
}
