CPP   54

Heap

Guest on 20th July 2022 04:33:05 PM

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <vector>
  4. using namespace std;
  5. char nodename[21][20],str1[20],str2[20];
  6. char v[21];
  7. int nodes,edges,limit,w;
  8. int groups[21],count,p[21];
  9. int best[21],from,to;
  10. int g[21][21],ng[21][21];
  11.  
  12. class Heap {
  13.         int array[30],w[30];
  14.         int size;
  15. public:
  16.         Heap() {size=0;}
  17.         void Insert(int a,int b) {
  18.                 int t;
  19.                 array[size]=a; w[size++]=b;
  20.                 if(b<w[0]) {
  21.                         t=array[0]; array[0]=array[size-1]; array[size-1]=t;
  22.                         t=w[0]; w[0]=w[size-1]; w[size-1]=t;
  23.                 }
  24.         }
  25.         int DeleteMin(int &weight) {
  26.                 int ans=array[0]; weight=w[0];
  27.                 if(size==1) { size=0; weight=w[0]; return ans; }
  28.                 int min=w[1],p=1;
  29.                 for(int i=2;i<size;i++)
  30.                         if(w[i]<min) {
  31.                                 min=w[i];
  32.                                 p=i;
  33.                         }
  34.                 array[0]=array[p]; w[0]=w[p];
  35.                 for(int i=p+1;i<size;i++) array[i-1]=array[i],w[i-1]=w[i];
  36.                 size--;
  37.                 return ans;
  38.         }
  39.         bool Update(int a,int b) {
  40.                 int i;
  41.                 for(i=0;i<size;i++)
  42.                         if(array[i]==a&&w[i]>b) { w[i]=b; break; }
  43.                 if(i==size) return false;
  44.                 int min=w[0],p=0;
  45.                 for(int i=1;i<size;i++)
  46.                         if(w[i]<min) {
  47.                                 min=w[i];
  48.                                 p=i;
  49.                         }
  50.                 int t;
  51.                 t=array[0]; array[0]=array[p]; array[p]=t;
  52.                 t=w[0]; w[0]=w[p]; w[p]=t;
  53.                 return true;
  54.         }
  55.         bool IsEmpty() { return size==0; }
  56. };
  57. void DFS(int u,int b)
  58. {
  59.         v[u]=true;
  60.         for(int w=0;w<nodes;w++)
  61.                 if(!v[w]&&ng[u][w]) {
  62.                         p[w]=u;
  63.                         int t=b;
  64.                         if(u==0) t=-99999999;
  65.                         if(b<ng[u][w]) t=ng[u][w];
  66.                         best[w]=t;
  67.                         DFS(w,t);
  68.                 }
  69. }
  70. int Find(char *s) {
  71.         for(int i=0;i<nodes;i++)
  72.                 if(strcmp(s,nodename[i])==0) return i;
  73.         strcpy(nodename[nodes++],s);
  74.         return nodes-1;
  75. }
  76. int main()
  77. {
  78.         int times;
  79.         strcpy(nodename[0],"Park");
  80.         scanf("%d",&times);
  81.         for(int c=0;c<times;c++) {
  82.                 if(c) puts("");
  83.                 memset(g,0,sizeof(g));
  84.                 memset(ng,0,sizeof(ng));
  85.                 scanf("%d",&edges);
  86.                 nodes=1;
  87.                 for(int i=0;i<edges;i++) {
  88.                         scanf("%s %s %d",str1,str2,&w);
  89.                         int a=Find(str1),b=Find(str2);
  90.                         g[a][b]=g[b][a]=w;
  91.                 }
  92.                 scanf("%d",&limit);
  93.                 memset(v,0,sizeof(v));
  94.                 count=0;
  95.                 for(int i=1;i<nodes;i++)
  96.                         if(!v[i]) {
  97.                                 count++;
  98.                                 Heap s;
  99.                                 s.Insert(i,0);
  100.                                 p[i]=-1;
  101.                                 while(!s.IsEmpty()) {
  102.                                         int w;
  103.                                         int u=s.DeleteMin(w);
  104.                                         v[u]=2; groups[u]=count;
  105.                                         if(p[u]!=-1) {
  106.                                                 ng[p[u]][u]=ng[u][p[u]]=w;
  107.                                         }
  108.                                         for(int j=1;j<nodes;j++) {
  109.                                                 if(g[u][j]) {
  110.                                                         if(v[j]==0) {
  111.                                                                 s.Insert(j,g[u][j]);
  112.                                                                 p[j]=u;
  113.                                                                 v[j]=1;
  114.                                                         }
  115.                                                         else if(v[j]==1) {
  116.                                                                 if(s.Update(j,g[u][j])) {
  117.                                                                         p[j]=u;
  118.                                                                 }
  119.                                                         }
  120.                                                 }
  121.                                         }
  122.                                 }
  123.                         }
  124.                         for(int i=1;i<=count;i++) {
  125.                                 int min=99999999,p;
  126.                                 for(int j=0;j<nodes;j++)
  127.                                         if(groups[j]==i&&g[0][j]&&g[0][j]<min) {
  128.                                                 min=g[0][j]; p=j;
  129.                                         }
  130.                                 ng[0][p]=ng[p][0]=min;
  131.                         }
  132.                         for(int i=count+1;i<=limit;i++) {
  133.                                 memset(v,0,sizeof(v));
  134.                                 best[0]=-99999999;
  135.                                 DFS(0,-99999999);
  136.                                 int min=0,s,t;
  137.                                 for(int i=0;i<nodes;i++)
  138.                                         if(g[0][i]&&(g[0][i]-best[i]<min)) {
  139.                                                 min=g[0][i]-best[i];
  140.                                                 s=t=i;
  141.                                         }
  142.                                 if(min==0) break;
  143.                                 while(true) {
  144.                                         if(g[p[s]][s]!=best[s]) s=p[s];
  145.                                         else {
  146.                                                 ng[p[s]][s]=ng[s][p[s]]=0;
  147.                                                 ng[0][t]=ng[t][0]=g[0][t];
  148.                                                 break;
  149.                                         }
  150.                                 }
  151.                         }
  152.                         int sum=0;
  153.                         for(int i=0;i<nodes;i++)
  154.                                 for(int j=0;j<nodes;j++)
  155.                                         if(ng[i][j]) {
  156.                                                 sum+=ng[i][j];
  157.                                         }
  158.                         printf("Total miles driven: %d\n",sum/2);
  159.         }
  160.         return 0;
  161. }

Raw Paste

Login or Register to edit or fork this paste. It's free.