【題目】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);
}
}
|