1034. Head of a Gang (30)

题目连接：https://www.patest.cn/contests/pat-a-practise/1034

这道题我自己写的代码中没用到什么数据结构，就是普通的逻辑关系，求和，比大小，但有好3个测试点没过：

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<vector>
  4 #include<string.h>
  5 
  6 using namespace std;
  7 typedef struct PNode{
  8     char ID[4];
  9     int time;
 10 }per;
 11 
 12 int N,K;
 13 vector<per>Gang[3005];
 14 
 15 int Have(char *s,vector<per>&p)
 16 {
 17     int i,flag=-1;
 18     for (i=0;i<p.size();i++)
 19     {
 20         if (strcmp(s,p[i].ID)==0)
 21         {
 22             flag=i;
 23             break;
 24         }
 25     }
 26     return flag;
 27 }
 28 
 29 int cmp(const void *a,const void *b)
 30 {
 31     return(strcmp((*(per*)a).ID,(*(per*)b).ID)>0);
 32 }
 33 
 34 int main()
 35 {
 36     scanf("%d %d",&N,&K);
 37     char A1[4],A2[4];
 38     int t,i,index=0,j,t1,t2;
 39     per tmp1,tmp2;
 40     int weight[3005]={0};
 41 
 42     tmp1.time=tmp2.time=0;
 43     scanf("%s%*c%s%d",&tmp1.ID,&tmp2.ID,&t);
 44     tmp1.time+=t;
 45     tmp2.time+=t;
 46     Gang[0].push_back(tmp1);
 47     Gang[0].push_back(tmp2);
 48     weight[0]=t;
 49    // printf("%s
",tmp2.ID);
 50     int fg=0;
 51     getchar();
 52     for (i=1;i<N;i++)
 53     {
 54         scanf("%s%*c%s%d",&tmp1.ID,&tmp2.ID,&t);
 55         getchar(); //printf("---%s %s
",tmp1.ID,tmp2.ID);
 56         fg=0;
 57         tmp1.time=tmp2.time=t;
 58         for (j=0;j<=index;j++)
 59         {
 60             t1=Have(tmp1.ID,Gang[j]);
 61             t2=Have(tmp2.ID,Gang[j]);
 62             if (t1>=0 && t2 <0)
 63             {Gang[j][t1].time+=t;
 64             Gang[j].push_back(tmp2);
 65             fg=1;
 66             weight[j]+=t;
 67             }
 68             else if (t2>=0 &&t1<0){
 69                 Gang[j][t2].time+=t;
 70                 Gang[j].push_back(tmp1);
 71                 fg=1;
 72                 weight[j]+=t;
 73             }
 74             else if (t1>=0 && t2>=0)
 75             {
 76                 Gang[j][t1].time+=t;
 77                 Gang[j][t2].time+=t;
 78                 fg=1;
 79                 weight[j]+=t;
 80             }
 81         }
 82         if (fg==0)
 83         {
 84             index++;
 85             Gang[index].push_back(tmp1);
 86             Gang[index].push_back(tmp2);
 87             weight[index]=t;
 88         }
 89     }
 90    // printf("%d
",index);
 91     per Head[3005];
 92     int cnt=0,tmpj,Maxt=-1;
 93 
 94     for (i=0;i<=index;i++)
 95     {
 96        // printf("%d %d
",Gang[i].size(),weight[i]);
 97         if (Gang[i].size()>2 &&weight[i]>K)
 98         {
 99             for (j=0;j<Gang[i].size();j++)
100             {
101                 if (Gang[i][j].time>Maxt)
102                 {
103                     Maxt=Gang[index][j].time;
104                     tmpj=j;
105                 }
106             }
107             strcpy(Head[cnt].ID,Gang[i][tmpj].ID);
108             Head[cnt].time=Gang[i].size();
109             cnt++;
110         }
111     }
112 
113     if (cnt==0){printf("0");return 0;}
114     qsort(Head,cnt,sizeof(Head[0]),cmp);
115     printf("%d
",cnt);
116     for (i=0;i<cnt;i++)
117     {
118         printf("%s %d
",Head[i].ID,Head[i].time);
119     }
120 
121     return 0;
122 }

View Code

希望大神能指出错误或提出测试样例。

参考了其他人的写法，才知道用到了映射，并查集/DFS等，主要参考了http://blog.csdn.net/xianyun2009/article/details/50176911的代码：

  1 #include<stdio.h>
  2 #include<vector>
  3 #include<map>
  4 #include<string>
  5 
  6 using namespace std;
  7 
  8 struct NODE{
  9     char a[4],b[4];
 10     int v;
 11 }node[1011];
 12 
 13 struct RES{
 14     string maxName;
 15     int maxV,totalV,member;
 16     RES():maxV(0),totalV(0),member(0){}
 17 };
 18 
 19 map<string,int>weight,lst;
 20 int index[3000]={0};
 21 
 22 int Find(int a)
 23 {
 24     if (index[a]<0)return a;
 25     else return index[a]=Find(index[a]);
 26 }
 27 
 28 void Union(int a,int b)
 29 {
 30     int a1,b1;
 31     a1=Find(a);
 32     b1=Find(b);
 33     if (a1!=b1)
 34     {
 35         if (index[a1]<=index[b1])
 36         {
 37             index[a1]+=index[b1];
 38             index[b1]=a1;
 39         }
 40         else if (index[a1]>index[b1])
 41         {
 42             index[b1]+=index[a1];
 43             index[a1]=b1;
 44         }
 45     }
 46 }
 47 
 48 int main()
 49 {
 50     int N,K;
 51     scanf("%d %d",&N,&K);
 52     int i;
 53    // char namea[4],nameb[4];
 54     for (i=0;i<N;i++)
 55     {
 56         scanf("%s%s%d",&node[i].a,&node[i].b,&node[i].v);
 57         weight[node[i].a]+=node[i].v;
 58         weight[node[i].b]+=node[i].v;
 59     }
 60 
 61     int cnt=0;
 62     for (map<string,int>::iterator it =weight.begin();it!=weight.end();it++)
 63     {
 64         index[cnt]=-1;
 65         lst[it->first]=cnt++;
 66     }
 67 
 68     for (i=0;i<N;i++)
 69     {
 70         Union(lst[node[i].a],lst[node[i].b]);
 71     }
 72 
 73     map<int,RES>res;
 74 
 75     for (map<string,int>::iterator it=weight.begin();it!=weight.end();it++)
 76     {
 77         int fa=Find(lst[it->first]);
 78         if (it->second>res[fa].maxV)
 79         {
 80             res[fa].maxV=it->second;
 81             res[fa].maxName=it->first;
 82         }
 83         res[fa].totalV+=it->second;
 84         res[fa].member++;
 85     }
 86 
 87     map<string,int>rs;
 88 
 89     for (map<int,RES>::iterator it=res.begin();it!=res.end();it++)
 90     {
 91         if (((it->second).member)>2 && ((it->second).totalV)/2>K)
 92         {
 93             rs[(it->second).maxName]=(it->second).member;
 94         }
 95     }
 96 
 97     printf("%d
",rs.size());
 98 
 99     for (map<string,int>::iterator it=rs.begin();it!=rs.end();it++)
100     {
101         printf("%s %d
",it->first.c_str(),it->second);
102     }
103 
104     return 0;
105 }

View Code