巢穴

about:blank

P1789

裸的朴素的prim...
wa了若干次..
1.判重数字忘记重置了..
2.relax写成dijkstra了....orz..奇妙的是样例还是过了..
还是要注意静态调试...
另外这道题太ooxx..数据量极大..用stl貌似会tle...
就这就够x的了..
Accepted 15708K 1594MS

#include <iostream>
#include <vector>
#include <string>
using namespace std;

const int MAXN=2001;
string s_vec[MAXN];
int edge[MAXN][MAXN];
int n;
int dist[MAXN];
bool hash[MAXN];
int answer=0;
#define INF 0x7fffffff
void prim()
{
     answer=0;
     memset(dist,0x7f,sizeof(dist));
     memset(hash,0,sizeof(hash));
     for (int i=0;i<n;i++)
         dist[i]=INF;
     
     dist[0]=0;
     for (int i=0;i<n;i++)
     {
         int min=INF;
         int u=-1;
         for (int j=0;j<n;j++)
         {
             if (hash[j]) continue;
             if (min>dist[j]) {min=dist[j];u=j;}
         }
         hash[u]=true;
         answer+=dist[u];
         for (int j=0;j<n;j++)
         {
             if (dist[j]>edge[u][j])
             {
              dist[j]=edge[u][j];
             }
         }
     }
     cout<<"The highest possible quality is 1/"<<answer<<"."<<endl;
     //system("pause");
     
}
int main()
{
    while(1)
    {
 //           s_vec.clear();
            cin>>n;
            if (0==n) break;
            for (int i=0;i<n;i++)
            {
             string str;
             cin>>s_vec[i];
            }
            for (int i=0;i<n;i++)
            {
                string str1=s_vec[i];
                for (int j=0;j<n;j++)
                {
                    if (i==j) {edge[i][j]=0;continue;}
                    string str2=s_vec[j];
                    int count=0;
                    for (int k=0;k<7;k++)
                     if (str1[k]!=str2[k]) count++;
                    edge[i][j]=count;
                }
            }
            prim();
            
    }
    return 0;
}

posted on 2009-10-06 12:05 Vincent 阅读(175) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理