poj 2485 (kruskal算法)
2024-10-14 23:23:35
/*kruskal算法*/
#include <iostream>
//#include <fstream>
#include <algorithm>
using namespace std;
/*708K 922MS*/
typedef struct _edge
{
int x,y;
int w;
}edge; int n;
int num;
//fstream fin; void kruskal(edge *e,int len);
int cmp(const void *a,const void *b); int main()
{
//fin.open("2485.txt",ios::in);
int t;
cin>>t;
while(t--)
{
cin>>n;
edge *e=new edge[n*n];
int temp;
int len=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
cin>>temp;
if(temp)
{
e[len].x=i;
e[len].y=j;
e[len++].w=temp;
}
}
kruskal(e,len);
cout<<num<<endl;
delete []e;
}
system("pause");
return 0;
} int cmp(const void *a,const void * b)
{
edge *a1=(edge *)a;
edge *b1=(edge *)b;
return a1->w-b1->w;
} void kruskal(edge *e,int len)
{
qsort(e,len,sizeof(edge),cmp);
int *s=new int[n];
memset(s,0,sizeof(int)*n);
int parts=0;
int max,u,v; for(int i=0;i<len;i++)
{
u=e[i].x; v=e[i].y;
if(!s[u]&&!s[v])
{
parts++;
s[u]=parts;
s[v]=parts;
max=e[i].w;
}
else if(s[u]&&!s[v])
{
s[v]=s[u];
max=e[i].w;
}
else if(s[v]&&!s[u])
{
s[u]=s[v];
max=e[i].w;
}
else
{
if(s[v]!=s[u])
{
int temp1=s[u];
int temp2=s[v];
if(temp1>temp2)
{
temp1=s[v];
temp2=s[u];
}
//更新
for(int j=0;j<n;j++)
{
if(s[j]==temp2)
s[j]=temp1;
else if(s[j]>temp2)
s[j]--;
}
max=e[i].w;
}
}
} num=max;
}
这时间 估计倒数了！
最新文章
- VS2013各个版本秘钥
- 【POJ 2528】Mayor’s posters（线段树+离散化）
- WinForm------GridControl显示每行的Indicator中的行号
- 转 Delphi中使用FastMM4结合View CPU避免内存泄漏
- MapReduce简介
- JAVA中操作符的优先级
- bzoj 1576 [Usaco2009 Jan]安全路经Travel（树链剖分，线段树）
- rpc远程调用开发
- Hibernate输出SQL语句以便调试
- sqlserver如何启动数据库邮件
- [Jobdu] 题目1367：二叉搜索树的后序遍历序列
- Linux Ubuntu 内核升级
- UIButton常用属性小结（编辑中。。。）
- Object.prototype.toString.call()方法浅谈
- 【Luogu2711】小行星（网络流，最大流）
- 远程服务器设置Mysql的操作权限
- MySQL 数据库 简单操作命令 （部分总结）
- PythonStudy——文件操作 File operation
- 数据库表字段，DEFAULT NULL与NOT NULL DEFAULT
- js-ES6学习笔记-Generator函数的应用