【题目】Windy想要挑选N个女生和M个男生。挑选一个人要花费10000元。
但是如果x与y有关系d，那么其中的一人被挑选后，再挑选另一人就只用花费10000-d元。
求挑选出来这N+M个人的最小花费。
我的想法是，将每个人看成一个点，若x与y有关系d，则看成有一条权值为10000-d的边，由于M和N的范围很大（1 ≤ N, M ≤ 10000）所以采用邻接表来存储图，然后求最小生成树。还要注意的是此题给出的图不一定是完全连通的，有可能要进行几次最小生成树才行。
  code
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
#define MAXR 100000+5
#define MAXN 20000+5
struct Relation
{
int v,cost,next;
}relation[MAXR];
bool visit[MAXN];
int p[MAXN];
int cnt;
int m,n;
int total,size,res;
struct node
{
int v,cost;
};
bool operator<(const node & n1,const node & n2)
{
return n1.cost>n2.cost;
}
priority_queue<node>q;
void prim()
{
node tmp;
for(int i=0;i<size;i++)
if(!visit[i])
{
tmp.v=i,tmp.cost=10000;
q.push(tmp);
break;
}
while(!q.empty() && total<size)
{
tmp=q.top();
q.pop();
if(visit[tmp.v])
continue;
visit[tmp.v]=1;
total++;
res+=tmp.cost;
for(int t=p[tmp.v];t!=-1;t=relation[t].next)
{
if(!visit[relation[t].v])
{
tmp.v=relation[t].v,tmp.cost=relation[t].cost;
q.push(tmp);
}
}
}
}
int main()
{
int t,r;
int xi,yi,di;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&r);
while(!q.empty())
q.pop();
memset(p,-1,sizeof(p));
cnt=0;
while(r--)
{
scanf("%d%d%d",&xi,&yi,&di);
yi+=n;
di=10000-di;
relation[cnt].v=yi;
relation[cnt].cost=di;
relation[cnt].next=p[xi];
p[xi]=cnt++;
relation[cnt].v=xi;
relation[cnt].cost=di;
relation[cnt].next=p[yi];
p[yi]=cnt++;
}
memset(visit,0,sizeof(visit));
total=0,size=m+n,res=0;
while(total!=size)
prim();
printf("%d\n",res);
}
}
|