Poj2421

#include <iostream>
#include<cstring>
using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;
        if (i && dist[t] == INF) return INF;
        if (i)res += dist[t];
        st[t] = true;
        for (int j = 1; j <= n; j ++ )
        {
            dist[j] = min(dist[j], g[t][j]);
        }
    }
    return res;
}


int main()
{

	int q,i,j,k;
	while (cin >> n)
	{
        memset(g,INF,sizeof g);
        memset(dist, 0x3f, sizeof dist);
        memset(st,false,sizeof st);
		for (i = 1; i <= n; i++)
		{
			for (j = 1; j <= n; j++)
			{
				cin >> g[i][j];
			}
		}
		cin >> q;
		int a, b;
		for (i = 0; i < q; i++)
		{
			cin >> a >> b;
            g[a][b]=g[b][a]=0;
		}
		cout << prim() << endl;
	}
    return 0;
}

#include <iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int NUM=103;
int S[NUM];//并查集
struct Edge{//定义边
    int u,v,w;
}edge[NUM*NUM];

bool cmp(Edge a,Edge b){return a.w<b.w;}

int find(int u){return S[u]==u?u:find(S[u]);}//查询并查集，返回u的根节点

int n,m=1;

int kruskal()
{
    int ans=0;
    for(int i=1;i<=n;i++)S[i]=i;//初始化，开始时每个点都是单独的集
    sort(edge+1,edge+1+m,cmp);
    for(int i=1;i<=m;i++)
    {
        int b=find(edge[i].u);//边的前端点u属于哪个集
        int c=find(edge[i].v);//边的后端点v属于哪个集
        if(b==c)continue;//产生圈，丢弃这个边
        S[c]=b;//合并
        ans+=edge[i].w;//计算MST
    }
    return ans;
}


int main()
{

	int q,k;
	int g[110][110];
	while (cin >> n)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				cin >> g[i][j];
			}
		}
		cin >> q;
		int a, b;
		for (int i = 0; i < q; i++)
		{
			cin >> a >> b;
            g[a][b]=g[b][a]=0;
		}
		for (int i = 1; i <= n; i++)
		{
            for(int j=i+1;j<=n;j++)
            {
                edge[m].u=i;
                edge[m].v=j;
                edge[m].w=g[i][j];
                m++;
            }
		}
		cout << kruskal() << endl;
	}
    return 0;
}