首页 > 代码库 > poj 3723 Conscription(最小生成树拓展）

poj 3723 Conscription(最小生成树拓展）

2024-07-15 13:51:44   221人阅读

Conscription
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 7702 Accepted: 2667

Description

Windy has a country, and he wants to build an army to protect his country. He has picked up N girls and M boys and wants to collect them to be his soldiers. To collect a soldier without any privilege, he must pay 10000 RMB. There are some relationships between girls and boys and Windy can use these relationships to reduce his cost. If girl x and boy y have a relationship d and one of them has been collected, Windy can collect the other one with 10000-d RMB. Now given all the relationships between girls and boys, your assignment is to find the least amount of money Windy has to pay. Notice that only one relationship can be used when collecting one soldier.

Input

The first line of input is the number of test case.
The first line of each test case contains three integers, N, M and R.
Then R lines followed, each contains three integers xi, yi and di.
There is a blank line before each test case.

1 ≤ N, M ≤ 10000
0 ≤ R ≤ 50,000
0 ≤ xi < N
0 ≤ yi < M
0 < di < 10000

Output

For each test case output the answer in a single line.

Sample Input

2

5 5 8
4 3 6831
1 3 4583
0 0 6592
0 1 3063
3 3 4975
1 3 2049
4 2 2104
2 2 781

5 5 10
2 4 9820
3 2 6236
3 1 8864
2 4 8326
2 0 5156
2 0 1463
4 1 2439
0 4 4373
3 4 8889
2 4 3133

Sample Output

71071
54223

Source

比较简单的一道最小生成树题，应该能够比较容易的就想到用最小生成树去做，这道题也有一点小技巧，就是在建图的时候把女生放在男生的后面，而且这个题没说图一定是连通图，也有可能不连通，开始看到这道题，我就觉得要进行排序所以用kruskal比较好，看了一些人的讲解说是最大生成森林，在建图的时候要注意，然后就是一道比较简单的题了；

我开始的思路是输入的时候，看到样例中有可能两个点中间有几条边，我们在这个题中间就要选择权值比较大的那条边，然后就考虑输入的问题，我输入的时候比较，一直不怎么好处理，那样处理对边数也不好控制，把女生直接放到男生后面，这样直接按权值排序，然后再判断他们直接的连通性。套用之前自己的模板就行；

在这道题中还遇到了一个小问题，开始在建图的时候，循环中i是从1开始的，后面排序的时候i是从0开始的，后面测试的时候答案一直不对，差那么一点，一直找原因，以后尽量要保持数组中的一致性，避免一些不必须的错误，思路要清晰；

下面是代码；

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10000+1;
struct node
{
    int u,v,w;
};
node map[5*maxn];
int father[2*maxn];
int n,m,r;
bool cmp(node x,node y)
{
    return x.w>y.w;
}
void Init()//对并查集初始化
{
    for(int i=0;i<n+m;i++)
        father[i]=i;
}
int find_set(int x)//带状态压缩的查找
{
    if(father[x]==x)
        return x;
    else
        return father[x]=find_set(father[x]);
}
/*bool union_set(int x,int y)//两个集合之间的合并
{
    x=find_set(x);
    y=find_set(y);
    if(x!=y)
    {
        father[y]=x;
        return true;
    }
    else
    {
        return false;
    }
}*/
int kruskal()
{
    int i,sum=0;
    Init();
    sort(map,map+r,cmp);
     for(i=0;i<r;i++)
   {
      /*if(union_set(map[i].u,map[i].v))//判断是否形成回路
              sum+=map[i].w;*/
     int x=find_set(map[i].u);//也可以直接在里面合并，这里的合并操作比较简单
     int y=find_set(map[i].v);
     if(x!=y)
     {
         father[y]=x;
         sum+=map[i].w;
     }
    }
   return sum;
}
int main()
{
   int t,x,y,d;
   scanf("%d",&t);
   while(t--)
   {
       scanf("%d%d%d",&n,&m,&r);
       for(int i=0;i<r;i++)
       {
            scanf("%d%d%d",&x,&y,&d);
             map[i].u=x;
             map[i].v=y+n;
             map[i].w=d;
       }
       printf("%d\n",(n+m)*10000-kruskal());
   }
    return 0;
}



联系
我们