POJ 2485 Prim 找最长的边

 A国没有高速公路，因此A国的交通很困难。政府意识到了这个问题并且计划建造一些高速公路，以至于可以在不离开高速公路的情况下在任意两座城镇之间行驶。

   A国的城镇编号为1到N, 每条高速公路连接这两个城镇，所有高速公路都可以在两个方向上使用。高速公路可以自由的相互交叉。

   A国政府希望尽量减少最长高速公路的建设时间（使建设的最长的高速公路最短），但是他们要保证每个城镇都可以通过高速公路到达任意一座城镇。

Input

第一个输入的数字T，代表着T组样例。

接下来输入一个N，代表一共有N个城镇。

然后读入一个N*N的矩阵，第i行第j列代表从i到j高速公路的距离。

Output

对于每个测试用例，您应输出一个包含整数的行，该整数是要构建的最长道路的长度，以便连接所有村庄，并且此值最小。

Sample Input

3

0 990 692

990 0 179

692 179 0

Sample Output

692

Hint

   Huge input,scanf is recommended.

上一道题改了两行,重写main函数就过了,真的弟弟.



#include <set>

#include <map>

#include <cmath>

#include <queue>

#include <bitset>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define ll long long

#define mm0(a) memset(a,0,sizeof(a))

#define mm(a,b) memset(a,b,sizeof(a))

#define each(a,b,c) for(int a=b;a<=c;a++)

#define de(x) cout << #x << " " << (x) <<endl

//#define de(x) cout <<""

#define rush() int T;scanf("%d",&T);each(kase,1,T)

#define scan(a,b) scanf("%d%d",&a,&b)

#define fin(a) scanf("%d",&a)

#include <iostream>

using namespace std;

//const int maxn = 400+5;

const int maxn = 2e3+5;

const int INF = 0x3f3f3f3f;

inline int read(){int s=0;char ch=getchar();for(; ch<'0'||ch>'9'; ch=getchar());for(; ch>='0'&&ch<='9'; ch=getchar())s=s*10+ch-'0';return s;}

bool vis[maxn];

int lowc[maxn];

int Prim(int cost[][maxn],int n)

{

    int ans=0;

    memset(vis,false,sizeof(vis));

    vis[0]=true;//从0开始的

    for(int i=1;i<n;i++)lowc[i]=cost[0][i];

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

    {

        int minc=INF;

        int p=-1;

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

        {

            if(!vis[j]&&minc>lowc[j])

            {

                minc=lowc[j];

                p=j;

            }

        }

        //de(minc);

            if(minc==-1)return -1;//又把==敲成一个等号了

            if(minc>ans)ans=minc;

            vis[p]=true;

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

            {

                if(!vis[j]&&lowc[j]>cost[p][j])

                    lowc[j]=cost[p][j];

            }

    }

    return ans;

}

int cost[maxn][maxn];

/*

1

3

0 990 692

990 0 179

692 179 0

*/

int main()

{

    rush()

    {

        int n;

        cin>>n;

        each(i,0,n-1)

        {

            each(j,0,n-1)

            {

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

            }

        }

        printf("%d\n",Prim(cost,n));

    }

}

巴特西

POJ 2485 Prim 找最长的边

最新文章

热门文章