1034. Head of a Gang（2、5）

两个测试点2、5过不去嘤嘤嘤先放着回头收拾你。 #include <stdio.h> #include <stdlib.h> #define MaxSize 17576 typedef struct Set { int time; int root; int total_time; }Set; int FindLoc(char p[]); int FindSet(int loc,Set Gang[]); void ConvertChar(char p[], int loc); int main() { int i, loc, n, k, t, Related[1000][3], set1, set2, num = 0; Set Gang[MaxSize]; char p1[4], p2[4]; for (i = 0; i < MaxSize; i++) { Gang[i].time = 0; Gang[i].total_time = 0; Gang[i].root = -1; } scanf("%d %d", &n, &k); for (i = 0; i < n; i++) { scanf("%s %s %d", p1, p2, &t); loc = FindLoc(p1);/*AAA-ZZZ与一个数一一对应*/ Gang[loc].time += t; Related[i][0] = loc; loc = FindLoc(p2); Gang[loc].time += t; Related[i][1] = loc; Related[i][2] = t; } for (i = 0; i < n; i++) {/*合并时将时间长的记为根*/ set1 = FindSet(Related[i][0], Gang); set2 = FindSet(Related[i][1], Gang); if (set1 != set2||set1==-1||set2==-1) if (Gang[set1].time>Gang[set2].time) { Gang[set1].root += Gang[set2].root; Gang[set1].total_time += Related[i][2];/*计算总时间*/ Gang[set2].root = set1; }else { Gang[set2].root += Gang[set1].root; Gang[set2].total_time += Related[i][2]; Gang[set1].root = set2; } else Gang[set2].total_time += Related[i][2]; } for (i = 0; i < MaxSize; i++) { if (Gang[i].total_time >k&&Gang[i].root < -2) num++; } printf("%d\n", num); if (num) for (i = 0; i < MaxSize; i++) if (Gang[i].total_time>k&&Gang[i].root<-2) { ConvertChar(p1, i); printf("%s %d\n", p1, -Gang[i].root); } return 0; } int FindLoc(char p[]) { int loc = 0; loc = (p[0] - 'A') * 676+ (p[1] - 'A') * 26 + (p[2] - 'A'); return loc; } int FindSet(int loc,Set Gang[]) { while (Gang[loc].root >= 0) loc = Gang[loc].root; return loc; } void ConvertChar(char p[], int loc) { p[3] = '\0'; p[2] = loc % 26 + 'A'; loc /= 26; p[1] = loc % 26+'A'; loc /= 26; p[0] = loc % 26 + 'A'; }