poj 1679 The Unique MST

第一次写次小生成树,没想到
思想就是:求一次最小生成树,记录所用到的边,然后不用所有第一次用到的边尝试构成构成最小生成树。
用Kruskal先求最小生成树,结果即为min,把所用到的边记录下来(这里是记录的对应的下表),然后枚举这些边,
每次去掉一个边求一次最小生成树,结果为tmin,如果能够成最小生成树并且tmin==min,则说明最小生成树不唯一
#include<iostream> //poj 1679
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX = 101;
int n, m;

struct edge
{
    int x;
    int y;
    int len;
}E[MAX*MAX];

int fa[MAX];
int indexEdge[MAX];
int index;
bool cmp(const edge &a, const edge &b)
{
    return a.len < b.len;
}

int find(int x)
{
    if(fa[x] == x)return x;
    return fa[x] = find(fa[x]);
}

int Kruskal(int location)  //不用location位置的边
{
    int ans = 0;
    int tx, ty;
    int cnt = 0;
    if (location == -1)index = 0;//location == -1 第一次求最小生成树,indexEdge[index]纪录第index用到的边的下标
    for(int k = 1; k <= n; k ++)fa[k] = k;

    for(int i = 0; i < m; i ++)
    {
        if(i == location)continue;
        tx = find(E[i].x);
        ty = find(E[i].y);
        if(tx != ty)
        {
            fa[tx] = ty;
            ans += E[i].len;
            cnt ++;
            if(location == -1)//第一次最小生成树的时候把location置为-1
            {
                indexEdge[index] = i;
                index ++;
            }
            if(cnt == n - 1)break;
        }
    }

    if(cnt == n - 1)return ans;
    return -1;
}

int main()
{
    int t, i;
    scanf("%d",&t);
    while(t --)
    {
        memset(E, 0, sizeof E);
        memset(indexEdge, 0, sizeof indexEdge);

        scanf("%d %d",&n, &m);

        for(i = 0; i < m; i ++)
            scanf("%d %d %d",&E[i].x, & E[i].y , & E[i].len);

        sort(E, E + m, cmp);
        
        int min = Kruskal(-1);    
        int tmin = (1<<20), temp;
        //cout << index << endl;
        
        for(i = 0; i < index; i ++)
        {
            //cout <<i <<' '<< indexEdge[i]<< endl;
            temp = Kruskal(indexEdge[i]);
            if(temp != -1 && temp < tmin)
                tmin = temp;
        }
        
        if(tmin == min)
            printf("Not Unique!\n");
        else printf("%d\n",min);
    }
                           
    return 0;
}

posted on 2010-12-11 16:48 田兵 阅读(400) 评论(0)  编辑 收藏 引用 所属分类: 图论题


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年12月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜