POJ 1258 Agri-Net|| POJ 2485 Highways MST

时间：2023-02-13 19:55:49

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;

}

相关文章