poj3723 Conscription【最大权森林】

本文主要是介绍poj3723 Conscription【最大权森林】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://poj.org/problem?id=3723
题意：需要招女兵n人，男兵m人，每招一人，需要花费10000元，但是如果已经招进来的人中有一些关系亲密的人，那就可以少花一些钱，比如u和v，有关系，那么就可以少花d元，问你招到所有人，最少花多少钱
解析：其实就相当于最大生成树，然后拿10000*（n+m）减去最大生成树的值，由于这里的图可能不连通，其实应该是最大生成森林，其实和最小生成树的做法很相似，用可以选择对边权取反，也可以选择逆序排序，都可以
prim+负值边权

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 2e5+100;
const int inf = 0x7fffffff;
struct node
{int v,w;node() {}node(int _v,int _w){v = _v;w = _w;}bool operator < (const node &b)const{return w>b.w;}
};
vector<node>G[maxn];
int vis[maxn];
int n1,n2,m;
void init(int n)
{for(int i=0;i<=n;i++)G[i].clear();memset(vis,0,sizeof(vis));
}
int prim(int s)
{int ans = inf;priority_queue<node>q;q.push(node(s,-inf));while(!q.empty()){node now = q.top();q.pop();if(vis[now.v])continue;vis[now.v] = 1;ans += now.w;for(int i=0;i<G[now.v].size();i++)q.push(G[now.v][i]);}return ans;
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d %d %d",&n1,&n2,&m);init(n1+n2);for(int i=0;i<m;i++){int x,y,z;scanf("%d %d %d",&x,&y,&z);G[x].push_back(node(n1+y,-z));G[n1+y].push_back(node(x,-z));}int ans = 0;for(int i=0;i<n1;i++){if(!vis[i])ans += prim(i);}printf("%d\n",10000*(n1+n2)+ans);}return 0;
}

kruskal+逆序排序

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 2e5+100;
const int inf = 0x7fffffff;
struct node
{int u,v,w;bool operator < (const node &b)const{return w>b.w;}
}a[maxn];
int fa[maxn];
int n1,n2,m;
void init(int n)
{for(int i=0;i<=n;i++)fa[i] = i;
}
int getFa(int x)
{if(x==fa[x])return x;return fa[x] = getFa(fa[x]);
}
void merge(int u,int v)
{int t1 = getFa(u);int t2 = getFa(v);if(t1!=t2)fa[t1] = t2;
}
int kruskal()
{sort(a,a+m);int ans = 0;for(int i=0;i<m;i++){int t1 = getFa(a[i].u);int t2 = getFa(a[i].v);if(t1!=t2){merge(a[i].u,a[i].v);ans += a[i].w;}}return -ans;
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d %d %d",&n1,&n2,&m);init(n1+n2);for(int i=0;i<m;i++){int x,y,z;scanf("%d %d %d",&x,&y,&z);a[i] = {x,n1+y,z};}printf("%d\n",10000*(n1+n2)+kruskal());}return 0;
}