kuangbin topic 6 POJ1789 Truck History

Title:
I'll give you a bunch of license plate numbers. Except for the original one, all the other license plate numbers are derived from a certain license plate number (change some letters). At the cost of different letters of two license plate numbers, ask you to figure out the minimum cost of all license plate numbers.
Explanation:
It took me a long time to understand the meaning of the question. As long as each license plate number is regarded as a point, the difference between each point can be calculated, and then the result can be calculated by using the minimum spanning tree. Prim is the best choice for dense graphs. Here I have a question.... 2000 * 7 * 2000 * 7 another 2000 * (2000 + 2000) does the time complexity not explode? Why can I use plain prim... It's too much data...
Extras:
After that, I went to try heap optimization and found out that there was super memory.... Did I write it wrong? Do you have a big man to try

//Plain prim
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
const int MAXN=2005;
int dis[MAXN];
bool vis[MAXN];
int map[MAXN][MAXN];
char s[MAXN][8];
int n;
void prim()
{
    int sum=0;
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)
    dis[i]=map[1][i];
    vis[1]=true;
    for(int i=1;i<=n;i++)
    {
        int MIN=INF,k=0;
        for(int j=1;j<=n;j++)
        if(!vis[j]&&MIN>dis[j])
        MIN=dis[j],k=j;
        vis[k]=true;
        for(int j=1;j<=n;j++)
        if(!vis[j]&&map[k][j]<dis[j])
        dis[j]=map[k][j];
    }
    for(int i=1;i<=n;i++) sum+=dis[i];
    printf("The highest possible quality is 1/%d.\n",sum); 
}
int main() 
{
    while(~scanf("%d",&n),n)
    {
        memset(map,INF,sizeof(map));
        for(int i=1;i<=n;i++)
        map[i][i]=0;
        for(int i=1;i<=n;i++)
        scanf("%s",&s[i]);
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(i==j)
            continue;
            int k=0;
            for(int ii=0;ii<7;ii++)
            {
                if(s[i][ii]!=s[j][ii])
                k++; 
            }
            if(map[i][j]>k)
            map[i][j]=map[j][i]=k;
        }
        prim();
    }
}
//Although it is over (metaphysics, because I still think about how to optimize when I estimate the time complexity), when the limit is 2000 strings, it will explode. It is time to learn heap optimization. 

Posted on Fri, 01 May 2020 05:59:52 -0700 by please_explain