hw0305.c

#include <stdio.h>
#include <stdlib.h>

#define MAX_SET_NUM 200005

typedef struct {
    int *array;
    int *attack;
    int size;
    int capacity;
    int Borrow_Health;
    int SumAttack;
} Heap;

typedef struct{
    int parent;
    int rank;
}Set;

Set DisJoinSet[MAX_SET_NUM];

void make_set(int x);
void link_set(int x,int y);
void union_set(int x,int y);
int Find_set(int x);


Heap* create_heap(int capacity);

void attack_heap(int x,int y);
void merge_heap(int x,int y,int tar);

void swap(int* a, int* b);
void heapify(Heap* heap, int index);
void insert(Heap* heap, int value,int attack); // 多insert attack
int extract_min(Heap* heap);
void print_heap(Heap* heap);

int n,m;
int h[MAX_SET_NUM];//health
int at[MAX_SET_NUM];//attack

Heap* knight_heap[MAX_SET_NUM];

void print_set(){
    for(int i=1;i<=n;i++){
        printf("set%d per=%d rank=%d\n",i,DisJoinSet[i].parent,DisJoinSet[i].rank);
    }    
    // for(int i=1;i<=n;i++){
    //     printf("knight %d: ",i);
    //     print_heap(knight_heap[i]);
    // } 
}
int main() {

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&h[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&at[i]);
    }
    
    for(int i=1;i<=n;i++){
        knight_heap[i]=create_heap(MAX_SET_NUM);
        insert(knight_heap[i] ,h[i] , at[i] );
        make_set(i);
    }
    print_set();
    for(int i=0;i<m;i++){

        int a,b;
        scanf("%d%d",&a,&b);
        int Aroot=Find_set(a),Broot=Find_set(b);

        //attack_heap( Broot,Aroot );//y(a) attack x(b)
        
        union_set(a, b);
        //merge_heap(Aroot,Broot , Find_set(a)); 
        print_set();
    }

    // for(int i=0;i<n;i++){
    //     int people = knight_heap[i]->size;
    //     printf("%d ",people);
    // }


    return 0;

}
//---------------------------------------setfunc

void make_set(int x){ //root is itself
    DisJoinSet[x].parent=x;
    DisJoinSet[x].rank=0;
}

void link_set(int x,int y){//link two root
    if( DisJoinSet[x].rank > DisJoinSet[y].rank ){
        DisJoinSet[y].parent = x;
    }else{
        DisJoinSet[x].parent = y;
        if( DisJoinSet[x].rank == DisJoinSet[y].rank ){
            DisJoinSet[y].rank++;
        }
    }
}

void union_set(int x,int y){//union by size
    link_set(Find_set(x),Find_set(y));
}

int Find_set(int x){//find root (path compression) 
    if( x != DisJoinSet[x].parent){
        DisJoinSet[x].parent=Find_set(DisJoinSet[x].parent);
    }
    return DisJoinSet[x].parent;
}

//------------------------------------------Heapfunc
void attack_heap(int x,int y){//y attack x
    if (knight_heap[x]->size == 0) {
        printf("Heap X is empty\n");
        return ;
    }
    int min = knight_heap[x]->array[0];
    int atk = knight_heap[x]->attack[0];
    int mem;
    knight_heap[x]->Borrow_Health += knight_heap[y]->SumAttack;
    while(min - knight_heap[x]->Borrow_Health  <=0 && knight_heap[x]->size != 0){ //check dead
        mem=extract_min(knight_heap[x]);
        knight_heap[x]->SumAttack -= atk ;
        min = knight_heap[x]->array[0];
        atk = knight_heap[x]->attack[0];
    }

}
void merge_heap(int x,int y,int tar){ //tar 2 to tar
    int tar2;
    if(tar == x ){
        tar2 = y;
    }else{
        tar2 = x;
    }
    knight_heap[tar]->SumAttack += knight_heap[tar2]->SumAttack;
    int health,atk;
    while (knight_heap[tar2]->size != 0){
        health  = knight_heap[tar2]->array[0];
        atk     = knight_heap[tar2]->attack[0];
        health -= knight_heap[tar2]->Borrow_Health;
        health += knight_heap[tar ]->Borrow_Health;
        insert( knight_heap[tar] , health ,atk );
    }
}
Heap* create_heap(int capacity) { //建立heap
    Heap* heap = (Heap*) malloc(sizeof(Heap));
    heap->array = (int*) malloc(capacity * sizeof(int));
    heap->attack= (int*) malloc(capacity * sizeof(int));
    heap->size = 0;
    heap->capacity = capacity;
    heap->Borrow_Health=0;
    heap->SumAttack=0;

    return heap;
}

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(Heap* heap, int index) {
    int smallest = index;
    int left_child = 2 * index + 1;
    int right_child = 2 * index + 2;

    if (left_child < heap->size && heap->array[left_child] < heap->array[smallest]) {
        smallest = left_child;
    }

    if (right_child < heap->size && heap->array[right_child] < heap->array[smallest]) {
        smallest = right_child;
    }

    if (smallest != index) {
        swap(&heap->array[index], &heap->array[smallest]);
        swap(&heap->attack[index], &heap->attack[smallest]);
        heapify(heap, smallest);
    }
}

void insert(Heap* heap, int value,int atk) {
    if (heap->size == heap->capacity) {
        printf("Heap is full, cannot insert more elements\n");
        return;
    }

    heap->array[heap->size] = value;
    heap->attack[heap->size] = atk;
    heap->SumAttack+=atk;
    int index = heap->size;
    heap->size++;

    while (index > 0 && heap->array[index] < heap->array[(index - 1) / 2]) {
        swap(&heap->array[index], &heap->array[(index - 1) / 2]);
        swap(&heap->attack[index], &heap->attack[(index - 1) / 2]);
        index = (index - 1) / 2;
    }
}


int extract_min(Heap* heap) {
    if (heap->size == 0) {
        printf("Heap is empty, cannot extract minimum element\n");
        return -1;
    }

    int min = heap->array[0];
    heap->size--;
    heap->array[0] = heap->array[heap->size];
    heapify(heap, 0);
    return min;
}

void print_heap(Heap* heap) {
    printf("Heap: ");
    printf(" size=%d ",heap->size);
    for (int i = 0; i < heap->size; i++) {
        printf(" ( %d | %d )", heap->array[i] ,heap->attack[i]);
    }
    printf("\n");
}