题目链接：Highways

没看题，看了输入输出。就有种似曾相识的感觉，果然和HDU1102 题相似度99%，可是也遇到一坑

cin输入居然TLE，cin的缓存不至于这么狠吧，题目非常水。矩阵已经告诉你了。就敲个模板就是了，5分钟。1A

题意就是打印，最小生成树的最大边权。改了改输入，水过

这个题完了。我的个人POJ计划进度以完毕 20/200，这当中主要是图论的题。等下周把POJ计划图论的题目打完，就回头打模拟！我就不信还能比图论难

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

const int N = 501;

const int INF = 1e8;

using namespace std;

int dis[N],mapp[N][N];

bool vis[N];

int n,ans;

void init()

{

    ans = 0;

    memset(vis,0,sizeof(vis));

}

void Prim()

{

    int pos,minn;

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

        dis[i] = mapp[0][i];

    vis[0] = true;

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

    {

        minn = INF;

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

        {

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

            {

                minn = dis[j];

                pos = j;

            }

        }

        vis[pos] = true ;

        if(minn > ans && minn!=INF)

            ans = minn;

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

        {

            if(!vis[k] && dis[k] > mapp[pos][k])

                dis[k] = mapp[pos][k];

        }

    }

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        init();

        scanf("%d",&n);

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

        {

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

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

        }

        Prim();

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

    }

    return 0;

}

HDU1102

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

using namespace std;

const int N = 110;

const int MAX = 9999999;

int map[N][N],n;

int dis[N],vis[N];

int a,b;

int sum = 0;

int PRIM()

{

    memset(dis,0,sizeof(dis));

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

        dis[i]=map[1][i];

    vis[1]=1;

    int wz = 0;

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

    {

        int min= MAX;

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

        {

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

            {

                min=dis[j];

                wz=j;

            }

        }

         if(min<MAX)

        {

            vis[wz]=1;

            sum+=min;

        }

        else

            return -1;

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

        {

            if(!vis[j]&&map[wz][j]<dis[j])

                dis[j]=map[wz][j];

        }

    }

    return sum;

}

int main()

{

    int q;

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

   {

       sum = 0;

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

    {

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

        {

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

        }

    }

    memset(vis,0,sizeof(vis));

    scanf("%d",&q);

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

    {

        scanf("%d%d",&a,&b);

        map[a][b] = 0;

        map[b][a] = 0;

    }

   sum = PRIM();

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

   }

    return 0;

}