POJ3723 Conscription 题解
POJ3723 Conscription 题解
题目链接:POJ3723 Conscription
题目描述:
Windy 有一个国家,他想建立一支军队来保护他的国家。他挑选了 \(N\) 个女孩和 \(M\) 个男孩,并想把他们招募为士兵。招募一名没有任何特权的士兵需要支付 10000 元。女孩和男孩之间存在一些关系,Windy 可以利用这些关系来降低费用。如果女孩 \(x\) 和男孩 \(y\) 之间存在关系 \(d\),并且其中一人已经被招募,那么 Windy 可以以 \(10000-d\) 元招募另一个人。现在给定所有女孩和男孩之间的关系,你的任务是求出 Windy 最少需要支付多少钱。注意,招募一名士兵时只能使用一条关系。
输入格式:
输入的第一行是测试用例数。
每个测试用例的第一行包含三个整数 \(N,M\,(1 \le N, M \le 10000)\) 和 \(R\,(0 \le R \le 50,000)\)。
接下来有 \(R\) 行,每行包含三个整数 \(x_i,y_i\,(0 \le x_i < N, 0 \le y_i < M)\) 和 \(d_i\,(0 < d_i < 10000)\)。
每个测试用例前有一个空行。
输出格式:
对于每个测试用例,在一行中输出答案。
首先,题目给出的格式 \(x_i\ y_i\ d_i\) 很像图论题
我们可以把每个人看作一个结点,为了防止男女编号相同的人搞混了,我们可以让女的编号为 \(1 \sim n\) ,男的编号为 \(n+1 \sim m\) ,显然这题要我们选出所有的结点且花费最小
我们可以发现答案如果存在环则会产生矛盾,例如:a招了b,b招了c,c招了a,这说不通
那是最小生成树吗?不一定
我们可以发现给定的这张图不一定是连通图,而我们要求的是花费最小的树型结构(感性理解下),那么这就是最大权森林问题,同样可以用最小生成树来求解(注:边权设为 \(-d_i\))
由于不一定是树,所以不需要记录连了多少边
代码如下
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
// POJ不给用万能头文件 qwq
using namespace std;
#define int long long
#define R register
#define MAXN (int)(2e4+50)
#define MAXM (int)(5e4+50)
template<typename T>inline void read(R T &k)
{
R char ch=getchar();R T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
k=x*f;
}
int Q,n,m,r;
int f[MAXN];
int find(R int x)
{return f[x]==x?x:f[x]=find(f[x]);}
inline void merge(R int u,R int v){f[find(u)]=find(v);} // 并查集
struct Edge
{
int u,v,w,next;
void clear(){u=v=w=next=0;} // 清空
bool operator<(const Edge &o)const
{return w<o.w;}
}e[MAXM];
int head[MAXN],pos=1;
void add(R int u,R int v,R int w)
{
e[pos]={u,v,w,head[u]};
head[u]=pos++;
}
int kruskal()
{
R int res=0;
sort(e+1,e+r+1);
for(R int i=1; i<=r; i++)
{
R int u=e[i].u,v=e[i].v,w=e[i].w;
if(find(u)!=find(v))
{merge(u,v);res+=w;}
}
return res;
}
void proc()
{
read(n);read(m);read(r);pos=1;
for(R int i=1; i<=n+m; i++)
f[i]=i;
for(R int i=1; i<=r; i++)
e[i].clear();
for(R int i=1,u,v,w; i<=r; i++)
{
read(u);read(v);read(w);
v+=n;++u;++v; // 题目是从0开始编号的,我不喜欢QwQ
add(u,v,-w);
}
printf("%lld\n",10000ll*(n+m)+kruskal()); // 别忘了加上每个人10000$的原价
}
signed main()
{
read(Q);
while(Q--)proc(); // 多组数据
return 0;
}




