Kruskal:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std; //#define debug
#if defined debug
#define CDBG(format,...) printf("File: "__FILE__", Line: %05d: "format"\n", __LINE__, ##__VA_ARGS__)
int open_file(){
FILE *fp ;
if((fp = freopen("input3.txt","r",stdin)) == NULL){
CDBG("error in freopen");
return -;
}
CDBG("success in freopen");
return ;
}
#else
#define CDBG(format,...) do{}while(0)
#endif #define N 510
int n,k,pre[N];
struct point
{
int x;
int y;
int len;
}p[N*N];
/*int cmp(const void * x,const void * y)
{
return ((point*)x)->len>((point*)y)->len?1:-1;
}*/ void swap(point &x,point &y)
{
point temp;
temp = x;
x = y;
y = temp; // 从指针改成数组就行了
} int choose_pivot(int i,int j )
{
return((i+j) /);
} void quicksort(point list[],int m,int n)
{
int key,i,j,k;
if( m < n)
{
k = choose_pivot(m,n);
if(m != k)
swap(list[m],list[k]);
key = list[m].len;
i = m+;
j = n;
while(i <= j)
{
while((i <= n) && (list[i].len <= key)) i++;
while((j >= m) && (list[j].len > key)) j--;
if( i < j)
swap(list[i],list[j]);
}
// 交换两个元素的位置
if(m != j)
swap(list[m],list[j]);
// 递归地对较小的数据序列进行排序
quicksort(list,m,j-);
quicksort(list,j+,n); } } int cmp(point x,point y)
{
return x.len<y.len;
}
int find(int x)
{
while(x!=pre[x]) x=pre[x];
return x;
}
void kruskal()
{
int i,mix,a,b;
mix=;
//sort(p,p+k,cmp);
for(i = ; i < k ;i++)
CDBG("%d ",p[i].len);
quicksort(p,,k-); //跟 sort 结果完全不一样
for(i = ; i < k ;i++)
CDBG("%d ",p[i].len);
for(i=;i<=n;i++)
pre[i]=i;// 可以初始化为 -1 等值
for(i=;i<k;i++)
{
a=find(p[i].x);
b=find(p[i].y);
if(a!=b)
{
if(p[i].len>mix)
mix=p[i].len;
pre[b]=a;
}
}
cout<<mix<<endl;
}
void input()
{
scanf("%d",&n);
k=;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
scanf("%d",&p[k].len);
if(i != j && p[k].len != ){
p[k].x=i;
p[k].y=j;
k++; //过滤掉ii 点
}
}
}
int main()
{
int T;
#ifdef debug
if(open_file() != )
return -;
#endif
scanf("%d",&T);
while(T--)
{
input();
kruskal();
}
return ;
}
void quicksort(int left, int right){
if (left > right)
return;
int l = left;
int r = right+;
path v, temp;
v = ipath[left];
while (){
while (l < r && ipath[--r].len >= v.len);
while (l < r && ipath[++l].len <= v.len);
if (l >= r) break;
temp = ipath[l];
ipath[l] = ipath[r];
ipath[r] = temp;
}
ipath[left] = ipath[l];
ipath[l] = v;
quicksort(left, l - );
quicksort(l + , right);
}Prime:
参考: http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html
/*
题目意思就是求最小生成树，并返回最长edge
求最小生成树一般有两种方法，prim算法 O[N^2]和kruskal算法 O[ElogE]，在这里我推荐使用prim算法，因为此题不是稀疏图，kruskal算法耗时较多（但也不会超时）
prim算法的基本思想
1.清空生成树，任取一个顶点加入生成树
2.在那些一个端点在生成树里，另一个端点不在生成树里的边中，选取一条权最小的边，将它和另一个端点加进生成树
3.重复步骤2，直到所有的顶点都进入了生成树为止，此时的生成树就是最小生成树
Prime()
{
//开始默认把1加入点集里
for(2~m)
dist[i]=map[1][i];
for(2~m)
{
//找跟相连的最短边
for(2~m)
{
if(!visit[j] && dist[j]<inf)
index="j";
}=""
visit[index]="1";
根据知道的点更新cost，这里方法有点像dijkstra，注意！！！=""
for(2~m)="" {="" if(!visit[j]="" &&="" cost[j]="">map[index][j])
cost[j]=map[index][j];
}
}
}
*/
#include<stdio.h>
#include<string.h> #define debug
#if defined debug
#define CDBG(format,...) printf("File:"__FILE__", Line:%05d: "format"\n", __LINE__, ##__VA_ARGS__)
#else
#define CDBG(format,...) do{}while(0)
#endif #define N 511
// n -> [3,500]
#define inf 0x3f3f3f3f
//distance -> [1,65536] int villages[N][N];
int visited[N];
int lowcost[N]; int open_file(){
FILE *fp ;
if((fp = freopen("input3.txt","r",stdin)) == NULL){
CDBG("error in freopen");
return -;
}
CDBG("success in freopen");
return ;
} void reset_visited(int n){
int i = ;
for( i = ; i<= n; i++){ visited[i] = ; lowcost[i] = ;}
}
//下面2个方法都可以
int prim(int start_p,int n){
int i,j,pos,min = ,result = ;
reset_visited(n);
//start at point 1
visited[start_p] = ; pos = start_p;
//set low array from point 1 to other point
for(i = ; i <= n; i++)
if(i != pos) {
lowcost[i] = villages[pos][i];
CDBG("set lowcost[%d] = %d",i,lowcost[i]);
}
//check n-1 times again ， 每次添加一个点到 最小树
for(i = ; i < n; i++){ // 使用 while循环代替 for 容易有一些问题
//find min distance 寻找下一个最短距离
min = inf;
for(j = ; j <= n; j++){
if(visited[j] == && lowcost[j] < min)
{
min = lowcost[j];//从未访问的点找到 最短距离的 点
pos = j;
CDBG("min = %d pos = %d j = %d",min,pos,j);
}
}
CDBG("min = %d pos = %d ",min,pos);
//add min distance;
if(result < min)
result = min; // 找最小树的最长距离 visited[pos] = ;
//update 更新当前最小的点 到 所有未访问过的点 的距离
for(j = ; j <= n; j++){
if(visited[j] == && lowcost[j] > villages[pos][j])
{
lowcost[j] = villages[pos][j];
CDBG("update lowcost[%d] = %d",j ,lowcost[j]);
}
}
}
return result;
} int prim(int n)
{
int u = ;
int i,j,k,start,min,max;
//memset(vis,0,sizeof(vis));
reset_visited(n);
for(i=;i<=n;i++)
if(i!=u)
lowcost[i]=villages[][i];
visited[]=true;
k=;
min=;max=;
for(i=;i<n;i++) //n-1条边
{
min=inf;
for(j=;j<=n;j++)
if(lowcost[j]<min&&!visited[j])
{
min=lowcost[j];
k=j;
}
if(min>max)
max=min;
visited[k]=true;
for(j=;j<=n;j++)
if(lowcost[j]>villages[k][j]&&!visited[j])
{
lowcost[j]=villages[k][j];
}
}
return max;
//cout<<max<<endl;
} void read_villages(int n){
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)
{
villages[i][j] = ;
scanf("%d",&villages[i][j]);
}
}
void check_villages(int n){
for(int i = ; i <= n; i++){
for(int j = ; j <= n; j++)
printf("%d ",villages[i][j]); // 应该是这个导致了 Output Limit Exceeded
printf("\n");
}
}
int main(){
int T,n;
#ifdef debug
if(open_file() != )
return -;
#endif scanf("%d",&T);
while(T--){
scanf("%d",&n);
read_villages(n);
//check_villages(n);
int ans=;
ans = prim(,n); // 可以从任意一点开始
//ans = prim(n);
printf("%d\n",ans);
} return ;
}