poj1789 2485 1258

poj1789

典型的prim算法，以每兩個string之間轉換的代價作為邊的權值

一開始用鄰接表一直RE，忘記将儲存邊的記錄清0.。。最後結果1500ms

然後直接換了數組，結果300+ms

我。。。

#include<iostream>  
#include <string>   
#include<vector>  
#include<algorithm>  
#include<set>  
#include<fstream>
#include<cmath>  
using namespace std;  
#define lch(i) ((i)<<1)  
#define rch(i) ((i)<<1|1)  
#define sqr(i) ((i)*(i))  
#define pii pair<int,int>  
#define mp make_pair  
#define FOR(i,b,e) for(int i=b;i<=e;i++)  
#define ms(a)   memset(a,0,sizeof(a))  
const int maxnum = 2005;  
  
int e[maxnum][maxnum];
int head[maxnum];
bool intree[maxnum];
int f=0;
//void add(int u,int v,int w){
//	e[f].v =v;
//	e[f].w = w;
//	e[f].next = head[u];
//	head[u]=f++;
//	e[f].v =u;
//	e[f].w = w;
//	e[f].next = head[v];
//	head[v]=f++;
//}



char v[maxnum][8];
int dis[maxnum];
int n,d;

int cmp(int a,int b){
	int num=0;
	FOR(i,0,6){
		if(v[a][i]!=v[b][i])num++;
	}
	return num;
}



int prim(){
	int sum=0;
	int rt;
	int treenum=0,mindis,min1;
	ms(intree);
	dis[1]=0;
	intree[1]=1;
	rt = 1;
	treenum++;
	while(treenum<n){
		mindis=100;
		FOR(i,2,n){
			if(!intree[i]&&dis[i]>e[rt][i])
				dis[i]=e[rt][i];
			if(!intree[i]&&dis[i]<mindis){
				mindis = dis[i];
				min1 = i;
			}
		}
		intree[min1]=1;
		rt = min1;
		treenum++;
		sum+=mindis;
	
	}
	return sum;
}


int main()  
{  
	/*ifstream fin("G:/1.txt");*/
	char type[8];
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		f=0;
		ms(e);ms(v);
		FOR(i,1,n)head[i]=-1;
		FOR(i,1,n){
			scanf("%s",v[i]);
			dis[i]=100;
		}
		FOR(i,1,n){
			FOR(j,1,i-1){
				e[i][j]=e[j][i]=cmp(i,j);
			}
		}
		printf( "The highest possible quality is 1/%d.\n",prim());

	}
}
           

poj2485 和上題基本一樣的算法，改了輸入，再将prim中的sum改為longest即可

poj1258 把上題longest 改回sum即可，基本上是prim的練習；