CHEER - Động viên đàn bò

Tác giả: hieult

Ngôn ngữ: C++

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
//#include <conio.h>

using namespace std;

#define MAX(a,b) ((a>b)?a:b)
#define CLEAR(A,N) (memset(A,0,(N)*sizeof(A[0])))

const int maxEdgeSize = 200005;
typedef struct{
        int x,y,cost;
}graph;

graph v[maxEdgeSize];
int ar[maxEdgeSize];

int findSet(int i){
    while(ar[i]!=i)
        i = ar[i];
    return i;
}

void makeUnion(int a,int p1,int b, int p2){
     int x = MAX(p1,p2);
     ar[a] = x;
     ar[b] = x;
     ar[p1] = x;
     ar[p2] = x;
}

int adjustUsingUnionFind(int a,int b)
{
    if(ar[a] == -1)  ar[a] = a;
    if(ar[b] == -1)  ar[b] = b;
    int p1 = findSet(a);
    int p2 = findSet(b);
    if(p1!=p2){
          makeUnion(a,p1,b,p2);
          return 1;
          }
    else return 0;
}

bool operator < (graph a, graph b)
{
     return a.cost < b.cost;
}

int main()
{
    //freopen("QBMST.in","r",stdin);
    int m,n,i,minimumCost,minn = 1000000,u[20001];
    scanf("%d %d",&m,&n);
    for(int i = 1;i<=m;i++)
    {
        scanf("%d",&u[i]);
        if(u[i]<minn)
            minn = u[i];
    }
   // printf("1");
    for(int i = 0;i<n;i++)
    {
        scanf("%d %d %d",&v[i].x,&v[i].y,&v[i].cost);
        v[i].cost = 2*v[i].cost+u[v[i].x]+u[v[i].y];
    }
    //printf("2");
    sort(v,v+n);
    for(int i = 0;i<=m;i++)
        ar[i] = -1;
    minimumCost = 0;
   // printf("3");
    for(int i = 0;i<n;i++)
    {
    
         if(adjustUsingUnionFind(v[i].x,v[i].y)==1)
         {
              minimumCost+= v[i].cost;
              //printf("%d\n",v[i].cost);
         }
    }
    printf("%d",minimumCost+minn);
    //getch();
}

Download