POJ 3723 Conscription（并查集建模）
【题目链接】 http://poj.org/problem?id=3723
【题目大意】
招募名单上有n个男生和m个女生，招募价格均为10000， 但是某些男女之间存在好感，则招募的时候， 可以降低与已招募人员中最大好感度的值， 求一定招募顺序使得招募总价格最小，输出最小价格
【题解】
对于存在好感度的男女之间连边，那么答案就是总价格减去最大权森林
【代码】
#include <cstdio>
#include <algorithm>
using namespace std;
int f[20005],n,m,r,T;
struct data{int x,y,c;}p[100005];
bool cmp(data a,data b){return a.c>b.c;}
int sf(int x){return x==f[x]?x:f[x]=sf(f[x]);}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&r);
for(int i=0;i<n+m;i++)f[i]=i;
for(int i=0;i<r;i++){
scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].c);
p[i].y+=n;
}sort(p,p+r,cmp);
long long ans=1LL*(n+m)*10000;
for(int i=0;i<r;i++){
if(sf(p[i].x)==sf(p[i].y))continue;
ans-=p[i].c;
f[sf(p[i].x)]=sf(p[i].y);
}printf("%lld\n",ans);
}return 0;
}
2022年9月14日 22:18
We advised contacting your Telugu teacher to get a chapter-wise practice model question paper for both levels of exams held under the school or board level and follow the link to download All AP SSC 10th Class Telugu Model Question Papers 2023 with Solutions. Every student everyone can download AP 10th Telugu Model Paper 2023 chapter-wise for paper-1, paper-2 exam theory, objective, AP 10th Telugu Question Paper multiple-choice questions (MCQ), Bit Question Bank with practice study material with IMP Question paper pdf with old scheme suggestions for AP 10th Class students 2023 to the Telugu Subject.