POJ 1258 Agri-Net

http://poj.org/problem?id=1258

水题。

题目就是让你求MST，连矩阵都给你了。

prim版

#include<cstdio>

const int MAXN=101;

const int INF=100000+10;

int map[MAXN][MAXN];

int dis[MAXN];

int n;

void prim()

{

	bool vis[MAXN]={0};

	for(int i=0;i<=n;i++)

		dis[i]=INF;

	int cur=1;

	vis[cur]=1;

	dis[cur]=0;

	for(int i=1;i<=n;i++)

	{

		for(int j=1;j<=n;j++)

			if(!vis[j] && dis[j] > map[cur][j])

				dis[j]=map[cur][j];

		int mini=INF;

		for(int j=1;j<=n;j++)

			if(!vis[j] && dis[j] <mini)

				mini=dis[cur=j];

		vis[cur]=1;

	}

}

int main()

{

	while(~scanf("%d",&n))

	{

		for(int i=1;i<=n;i++)

			for(int j=1;j<=n;j++)

				scanf("%d",&map[i][j]);

		prim();

		int ans=0;

		for(int i=1;i<=n;i++)

			ans+=dis[i];

		printf("%d\n",ans);

	}

	return 0;

}

kruskal

#include<cstdio>

#include<algorithm>

using namespace std;

const int MAXN=101;

const int INF=100000+10;

int fa[MAXN];

int n;

struct data

{

	int x,y;

	int dis;

}a[MAXN*MAXN];

bool operator< (const data& c,const data &d)

{

	return c.dis<d.dis;

}

int find(int cur)

{

	return cur==fa[cur]? cur:fa[cur]=find(fa[cur]);

}

int main()

{

	while(~scanf("%d",&n))

	{

		int len=0;

		for(int i=1;i<=n;i++)

			for(int j=1;j<=n;j++)

			{

				scanf("%d",&a[len].dis);

				a[len].x=i;

				a[len].y=j;

				len++;

			}

		sort(a,a+len);

		int ans=0;

		for(int i=1;i<=n;i++)

			fa[i]=i;

		for(int i=0;i<len;i++)

		{

			int rootx=find(a[i].x);

			int rooty=find(a[i].y);

			if(rootx!=rooty)

			{

				fa[rootx]=rooty;

				ans+=a[i].dis;

			}

		}

		printf("%d\n",ans);

	}

	return 0;

}

-------------------------------------------------我是可爱的分割线-------------------------------------------------

poj2485  Highways

http://poj.org/problem?id=2485

题目要求求MST上最长的边。

上面的代码一改就过了。。。。

prim

#include<cstdio>

const int MAXN=520;

const int INF=100000+10;

int map[MAXN][MAXN];

int dis[MAXN];

int n;

void prim()

{

	bool vis[MAXN]={0};

	for(int i=0;i<=n;i++)

		dis[i]=INF;

	int cur=1;

	vis[cur]=1;

	dis[cur]=0;

	for(int i=1;i<=n;i++)

	{

		for(int j=1;j<=n;j++)

			if(!vis[j] && dis[j] > map[cur][j])

				dis[j]=map[cur][j];

		int mini=INF;

		for(int j=1;j<=n;j++)

			if(!vis[j] && dis[j] <mini)

				mini=dis[cur=j];

		vis[cur]=1;

	}

}

int main()

{

	int T;

    scanf("%d",&T);

    while(T--)

    {

		scanf("%d",&n);

		for(int i=1;i<=n;i++)

			for(int j=1;j<=n;j++)

				scanf("%d",&map[i][j]);

		prim();

		int ans=0;

		for(int i=1;i<=n;i++)

		{

			if(ans < dis[i])

				ans=dis[i];

		}

		printf("%d\n",ans);

	}

	return 0;

}

kruskal

#include<cstdio>

#include<algorithm>

using namespace std;

const int MAXN=520;

const int INF=100000+10;

int fa[MAXN];

int n;

struct data

{

	int x,y;

	int dis;

}a[MAXN*MAXN];

bool operator< (const data& c,const data &d)

{

	return c.dis<d.dis;

}

int find(int cur)

{

	return cur==fa[cur]? cur:fa[cur]=find(fa[cur]);

}

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d",&n);

		int len=0;

		for(int i=1;i<=n;i++)

			for(int j=1;j<=n;j++)

			{

				scanf("%d",&a[len].dis);

				a[len].x=i;

				a[len].y=j;

				len++;

			}

		sort(a,a+len);

		int ans=0;

		for(int i=1;i<=n;i++)

			fa[i]=i;

		for(int i=0;i<len;i++)

		{

			int rootx=find(a[i].x);

			int rooty=find(a[i].y);

			if(rootx!=rooty)

			{

				fa[rootx]=rooty;

				ans=a[i].dis;

			}

		}

		printf("%d\n",ans);

	}

	return 0;

}

最新文章

1. 在Ubuntu 12.4 下安装 nginx, MySQL, PHP
2. c++中resize函数怎么用
3. Centos6.6下安装MySQL5.6
4. [CentOs7]图形界面
5. QtCreator下运行opencv出现realloc():pointer invalid
6. phpcms v9调用多个栏目下文章的方法
7. hadoop单节点windows 7 环境搭建
8. nginx reload
9. stdcall与cdecl的区别
10. BZOJ 4597 随机序列
11. Oracle 的证也会过期咯
12. Android再学习-20141111-Android应用的七大件
13. flex 用footerdatagrid做列的汇总合计
14. AngularJS学习笔记5
15. ThreadLocal源码分析：（二）get()方法
16. cesium-navigation 使用(非require，es6引用)
17. keepalived 安装及配置
18. elastic-job详解（三）：Job的手动触发功能
19. 如何在 ajax 外拿到 ajax 的数据？？？和ajax的参数
20. VS2010安装项目程序打包操作详解

热门文章

1. ActiveMQ学习总结（2）——ActiveMQ入门实例教程
2. error c2572重定义默认參数
3. 南阳oj 士兵杀敌（二） 题目116 NYOJ 数据结构
4. Linux下进程终止过程
5. php课程 18-60 cookie和session的最主要区别是什么
6. BZOJ2244: [SDOI2011]拦截导弹(CDQ分治，二维LIS，计数)
7. vector转数组
8. KNIMI数据挖掘建模与分析系列_002_利用KNIMI做商超零售关联推荐
9. Relaxation step（Dijkstra's 最短路径算法）
10. HTML基础-第一讲