URAL 1982 最小生成树变形

这题苦逼的组队赛的时候想歪了，然后竟然不知道是最小生成树，自己写的没过，宝哥一看就看出最小生成树了……唉……非模板题都看不出来，得练练啊……

刚刚又交了好多发才过，最后一发不过的话都想放弃了，没想到真过了，哈哈……

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define sc(a,b) scanf("%d%d",&a,&b)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 1000005
#define MN 100010
#define INF 55566677
#define eps 1e-7
using namespace std;
typedef long long ll;
struct node
{
    int u,v,w,next;
} e[101001];
int f[1001],cnt,a[101];
bool cmp(node a,node b)
{
    return a.w<b.w;
}
int find(int x)
{
    f[x]==x?x:f[x]=find(f[x]);
}
void add(int u,int v,int w)
{
    e[cnt].u=u; e[cnt].v=v; e[cnt++].w=w;
}
int main()
{
    int n,k,i,j,m,sum=0,sum1=0,sum2=0;
    sc(n,k);
    for(i=0; i<=n; i++) f[i]=i;
    sca(a[0]);sum1++;
    for(i=1;i<k;i++)
    {
        sca(a[i]),sum1++;  //刚开始这里用的是标记访问过，然后一直WA，然后直接改成这样就过了，哎呀，晕……原来是用标记是有BUG的
        int x=find(a[i]);
        int y=find(a[i-1]);
        f[x]=y;
    }
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
        {
            sca(m);
            if(i!=j) add(i,j,m),add(j,i,m);
        }
    sort(e,e+cnt,cmp);
    for(i=0; i<cnt; i++)
    {
        if(sum2==n-sum1) break;
        int x=find(e[i].u);
        int y=find(e[i].v);
        if(x!=y) f[x]=y,sum+=e[i].w,sum2++;
    }
    pri(sum);
    return 0;
}

URAL 1982 最小生成树变形,布布扣,bubuko.com

URAL 1982 最小生成树变形

原文：http://blog.csdn.net/u011466175/article/details/23022207