Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

眼睁睁的把最小生成树打成了单源最短路径，prim和dij真的好像啊23333

Posted by 14020130063 at 2015-10-19 01:26:03 on Problem 1789

***********这是正确的prim*************

#include<cstdio>
#include<iostream>
using namespace std;
#define N 2005
#define INF 1e8
int G[N][N],dist[N],n,ans;
bool vis[N];
char ch[N][8];
void prim()
{
    int m,u;
    for(int i=1;i<=n;i++)
    {
        vis[i]=false;
        dist[i]=G[1][i];
    }
    vis[1]=true;ans=0;
    for(int i=1;i<n;i++)
    {
        m=INF;
        for(int j=1;j<=n;j++)
        {
            if((!vis[j])&&m>dist[j])
                m=dist[u=j];
        }
        vis[u]=true;
        ans+=dist[u];
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]) dist[j]=min(dist[j],G[u][j]);
        }
    }
}
int main()
{
    while(scanf("%d",&n)&&n!=0)
    {
        for(int i=1;i<=n;i++)
            scanf("%s",ch[i]);
        for(int i=1;i<=n;i++)
        {
            G[i][i]=0;
            for(int j=i+1;j<=n;j++)
            {
                G[i][j]=0;
                for(int k=0;k<7;k++)
                {
                    if(ch[i][k]!=ch[j][k])
                        G[i][j]++;
                }
                G[j][i]=G[i][j];
            }
        }
        prim();
        printf("The highest possible quality is 1/%d.\n",ans);
    }
    return 0;
}


*****这是打错了的dij，亮点在dist数组的更新上，上下俩程序的唯一差别*****


#include<cstdio>
#include<iostream>
using namespace std;
#define N 2005
#define INF 1e8
int G[N][N],dist[N],n,ans;
bool vis[N];
char ch[N][8];
void prim()
{
    int m,u;
    for(int i=1;i<=n;i++)
    {
        vis[i]=false;
        dist[i]=G[1][i];
    }
    vis[1]=true;ans=0;
    for(int i=1;i<n;i++)
    {
        m=INF;
        for(int j=1;j<=n;j++)
        {
            if((!vis[j])&&m>dist[j])
                m=dist[u=j];
        }
        vis[u]=true;
        ans+=dist[u];
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]) dist[j]=min(dist[j],dist[u]+G[u][j]);
        }
    }
}
int main()
{
    while(scanf("%d",&n)&&n!=0)
    {
        for(int i=1;i<=n;i++)
            scanf("%s",ch[i]);
        for(int i=1;i<=n;i++)
        {
            G[i][i]=0;
            for(int j=i+1;j<=n;j++)
            {
                G[i][j]=0;
                for(int k=0;k<7;k++)
                {
                    if(ch[i][k]!=ch[j][k])
                        G[i][j]++;
                }
                G[j][i]=G[i][j];
            }
        }
        prim();
        printf("The highest possible quality is 1/%d.\n",ans);
    }
    return 0;
}


WA了一发，然后470几MS水过。。。

Followed by:

同。。。。T^T (0) G_lory 2015-11-06 18:46:08

Post your reply here:

User ID:
Password:
Title:

Content:

> ***********这是正确的prim*************
> 
> #include<cstdio>
> #include<iostream>
> using namespace std;
> #define N 2005
> #define INF 1e8
> int G[N][N],dist[N],n,ans;
> bool vis[N];
> char ch[N][8];
> void prim()
> {
>     int m,u;
>     for(int i=1;i<=n;i++)
>     {
>         vis[i]=false;
>         dist[i]=G[1][i];
>     }
>     vis[1]=true;ans=0;
>     for(int i=1;i<n;i++)
>     {
>         m=INF;
>         for(int j=1;j<=n;j++)
>         {
>             if((!vis[j])&&m>dist[j])
>                 m=dist[u=j];
>         }
>         vis[u]=true;
>         ans+=dist[u];
>         for(int j=1;j<=n;j++)
>         {
>             if(!vis[j]) dist[j]=min(dist[j],G[u][j]);
>         }
>     }
> }
> int main()
> {
>     while(scanf("%d",&n)&&n!=0)
>     {
>         for(int i=1;i<=n;i++)
>             scanf("%s",ch[i]);
>         for(int i=1;i<=n;i++)
>         {
>             G[i][i]=0;
>             for(int j=i+1;j<=n;j++)
>             {
>                 G[i][j]=0;
>                 for(int k=0;k<7;k++)
>                 {
>                     if(ch[i][k]!=ch[j][k])
>                         G[i][j]++;
>                 }
>                 G[j][i]=G[i][j];
>             }
>         }
>         prim();
>         printf("The highest possible quality is 1/%d.\n",ans);
>     }
>     return 0;
> }
> 
> 
> *****这是打错了的dij，亮点在dist数组的更新上，上下俩程序的唯一差别*****
> 
> 
> #include<cstdio>
> #include<iostream>
> using namespace std;
> #define N 2005
> #define INF 1e8
> int G[N][N],dist[N],n,ans;
> bool vis[N];
> char ch[N][8];
> void prim()
> {
>     int m,u;
>     for(int i=1;i<=n;i++)
>     {
>         vis[i]=false;
>         dist[i]=G[1][i];
>     }
>     vis[1]=true;ans=0;
>     for(int i=1;i<n;i++)
>     {
>         m=INF;
>         for(int j=1;j<=n;j++)
>         {
>             if((!vis[j])&&m>dist[j])
>                 m=dist[u=j];
>         }
>         vis[u]=true;
>         ans+=dist[u];
>         for(int j=1;j<=n;j++)
>         {
>             if(!vis[j]) dist[j]=min(dist[j],dist[u]+G[u][j]);
>         }
>     }
> }
> int main()
> {
>     while(scanf("%d",&n)&&n!=0)
>     {
>         for(int i=1;i<=n;i++)
>             scanf("%s",ch[i]);
>         for(int i=1;i<=n;i++)
>         {
>             G[i][i]=0;
>             for(int j=i+1;j<=n;j++)
>             {
>                 G[i][j]=0;
>                 for(int k=0;k<7;k++)
>                 {
>                     if(ch[i][k]!=ch[j][k])
>                         G[i][j]++;
>                 }
>                 G[j][i]=G[i][j];
>             }
>         }
>         prim();
>         printf("The highest possible quality is 1/%d.\n",ans);
>     }
>     return 0;
> }
> 
> 
> WA了一发，然后470几MS水过。。。

Home Page Go Back To top