在线精品亚洲,国产免费观看久久,欧美日韩在线另类

P1789

裸的樸素的prim...
wa了若干次..
1.判重?cái)?shù)字忘記重置了..
2.relax寫成dijkstra了....orz..奇妙的是樣例還是過了..
還是要注意靜態(tài)調(diào)試...
另外這道題太ooxx..數(shù)據(jù)量極大..用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 閱讀(197) 評論(0) 編輯收藏引用所屬分類: 數(shù)據(jù)結(jié)構(gòu)與算法

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: P3368 P2352 dinic P3273 P2104 ctsc2000 丘比特的煩惱 usaco 4.3 lgame P3267 P1276 P1837

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

巢穴

My Links

Blog Stats

News

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

文章檔案

Link

搜索

最新評論

閱讀排行榜

評論排行榜

P1789