[2497] Maximum Star Sum of a Graph

ㄜ.......果然會超過memory （嗎）

先貼個runtime error 版....

因為不想用動態加linked list node 的方式，所以先算了每個node 有幾個edge, 用一個int array 去存它，當node 數目是10000個的時候, 乘上sizeof(int) 就會爆炸了（的樣子）

所以結論是還是要用linked list 嗎！！！（如果沒有要改成C++的vector 的話 Orz)

int comp(const void *a, const void *b)

{

return ( *(int*)b - *(int*)a);

}

int maxStarSum(int* vals, int valsSize, int** edges, int edgesSize, int* edgesColSize, int k) {

if (edgesSize == 0 || k==0)

{

qsort(vals, valsSize, sizeof(int), comp);

return (vals[0]);

}

int *sizeArray = calloc (valsSize,sizeof(int)*valsSize);

int *sizeArrayIdx = calloc (valsSize,sizeof(int)*valsSize);

for (int i=0; i<edgesSize; i++)

{

sizeArray[edges[i][0]]++;

sizeArray[edges[i][1]]++;

}

int **pair = calloc (valsSize, sizeof(int*)* valsSize);

for (int i=0; i<valsSize; i++)

pair[i] = calloc(sizeArray[i], sizeof(int) * sizeArray[i]);

for (int i=0; i<edgesSize; i++)

{

pair[edges[i][0]][sizeArrayIdx[edges[i][0]]++]= vals[edges[i][1]];

pair[edges[i][1]][sizeArrayIdx[edges[i][1]]++]= vals[edges[i][0]];

}

int max = INT_MIN;

for (int i=0;i<valsSize; i++)

{

if (sizeArray[i]==0)

continue;

qsort(pair[i], sizeArray[i], sizeof(int), comp);

int tmp = vals[i];

for (int j=0;j<k;j++)

{

if (tmp > max)

max = tmp;

tmp += pair[i][j];

if (j==sizeArray[i]-1)

break;

}

if (tmp > max)

max = tmp;

}

return max;

}

然後～竟然給我寫出了linked list 的版本！天啊我真是太為自己感到驕傲了（激動落淚）

雖然有些小偷吃步的地方～ sorting 是拿寫好的function 來run. 

然後我的第一個node不會進去sorting, 讓我可以處理它沒有edge連出去，或是它自己就會是最大值的情況。 另外因為linked list sorting 過了，所以一旦加了下一個值沒有變大（通常是負數（吧））就讓它break 掉了。以上。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){

if (list1 ==NULL)

return list2;

if (list2 == NULL)

return list1;

if (list1->val > list2->val)

{

list1->next = mergeTwoLists(list1->next, list2);

return list1;

}

else

{

list2->next = mergeTwoLists(list1, list2->next);

return list2;

}

}

struct ListNode* sortList(struct ListNode* head){

if (head == NULL || head->next == NULL)

return head;

struct ListNode *pre , *fast , *slow;

fast=head;

slow=head;

while (fast!= NULL && fast->next != NULL)

{

pre=slow;

slow =slow->next;

fast=fast->next;

if (fast->next != NULL)

fast=fast->next;

}

pre->next = NULL;

return mergeTwoLists(sortList(head),sortList(slow));

}

int maxStarSum(int* vals, int valsSize, int** edges, int edgesSize, int* edgesColSize, int k) {

struct ListNode *nextNode[valsSize];

struct ListNode* pair[valsSize];

for (int i=0;i<valsSize; i++)

{

pair[i] = calloc (1,sizeof( struct ListNode));

pair[i]->val = vals[i];

pair[i]->next = NULL;

nextNode[i] = pair[i];

}

for (int i=0; i<edgesSize; i++)

{

int idx = edges[i][0];

{

struct ListNode* ptr = calloc (1,sizeof( struct ListNode));

ptr->val = vals[edges[i][1]];

ptr->next = NULL;

nextNode[idx]->next = ptr;

nextNode[idx] = ptr;

}

idx = edges[i][1];

{

struct ListNode* ptr = calloc (1,sizeof( struct ListNode));

ptr->val = vals[edges[i][0]];

ptr->next = NULL;

nextNode[idx]->next = ptr;

nextNode[idx] = ptr;

}

}

int max = INT_MIN;

for (int i=0;i<valsSize; i++)

{

struct ListNode* ptr = pair[i];

struct ListNode* p2;

p2 = ptr->next;

if (p2 != NULL)

ptr->next = sortList(p2);

int tmp = ptr->val;

if (tmp > max)

max = tmp;

int idx = 0;

ptr = ptr->next;

while (idx < k && ptr != NULL)

{

if (tmp + ptr->val < tmp)

break;

tmp += ptr->val;

if (tmp > max)

max = tmp;

ptr = ptr->next;

idx++;

}

}

return max;

}

#if 0

{

for (int i=0;i<valsSize; i++)

{

printf(" i %d:\n",i);

struct ListNode* ptr = pair[i];

while (ptr != NULL)

{

printf(" [%d] ", ptr->val);

ptr = ptr->next;

}

printf("\n");

}

}

#endif