附代码:
#include<cstdio>
#include<climits>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int N=207;
int max_[N][N]; // 最小权边邻接点集合,最小权边值集合
struct edge {  //  边信息
    int u,v,w;
    friend bool operator<(edge const&L,edge const&R) {
        return L.w<R.w;
    }
} ;
struct edge_ {
    int v,w;
    edge_(int x,int y ) {
        v = x; w = y;
    }
};
vector<edge_> ve[N];
edge E[N*N];
bool e[N];
class UF {  // 并查集
public:
    void makeset(int i ) { parent[i] = i; rank[i] = 0; }
    void Union(int x,int y) { link(Find(x),Find(y)); }
    int Find(int x) {
        if(parent[x]!=x) parent[x] = Find(parent[x]);
        return parent[x];
    }
    bool Joint(int x,int y){ return Find(x)==Find(y); }
private:
   int parent[N],rank[N];
   void link(int x,int y) {
        if(rank[y]<rank[x]) {
             parent[y] = x;
        }
        else {
             parent[x] = y;
             if(rank[x]==rank[y]) ++rank[y];
        }
   }
};
int kruscal(edge*E,int n,int m)
{
    UF uf;
    for(int i=1;i<=n;++i) uf.makeset(i);
    for(int i=0;i<m; ++i) e[i]=false;;
    std::sort(E,E+m);
    int sum = 0;
    for(int i=0,j=0;i<m&&j<n-1;++i) {
        int x=E[i].u;
        int y=E[i].v;
        if(!uf.Joint(x,y)) {
              sum += E[i].w;
              uf.Union(x,y);
              ve[x].push_back(edge_(y,E[i].w));
              ve[y].push_back(edge_(x,E[i].w));
              e[i] = true;
              ++j ;
        }
    }
    return sum;
}
void getmax_(int u,int n)
{
    memset(max_[u],0xff,sizeof(max_[u]));
    queue<int> Q;
    Q.push(u);
    while( !Q.empty() ) {
        int v = Q.front() ; Q.pop();
        for(int i=0;i<(int)ve[v].size();++i)
        {
            edge_ const &x = ve[v][i];
            if(max_[u][x.v]==-1&&x.v!=u) {
               if(u==v|| x.w>max_[u][v]) max_[u][x.v] = x.w;
               else max_[u][x.v] = max_[u][v];
               Q.push(x.v);
            }
        }
    }
}
int mst_sec(edge*E,int n,int m,int sum)
{
    for(int i=1;i<=n;++i) getmax_(i,n); // 求树上任意两点间的最大边权?
    int mx=INT_MAX;
    for(int i=0;i<m;++i) {
            if( e[i] == false ) {
                if(mx>E[i].w-max_[E[i].u][E[i].v])
                    mx=E[i].w-max_[E[i].u][E[i].v];
            }
    }
    return sum - mx;
}
int main()
{
   int n,m,test;
   scanf("%d",&test);
   for( ;  test ;  --test)
   {
       scanf("%d%d",&n,&m);
       for(int i=0;i<m;++i)
       {
           int a,b,w;
           scanf("%d%d%d",&a,&b,&w);
           E[i].u = a; E[i].v = b; E[i].w = w;
       }
       int res = kruscal(E,n,m);
       if(res == mst_sec(E,n,m,res))  printf("Not Unique!\n");
       else printf("%d\n",res);
       for(int i =1;i<=n;++i) ve[i].clear();
   }
   return 0;
}

• Re:此题很有问题.....用kruscal做的,不用sort就AC...加上sort就RE.... (3078) caotong0 2010-08-02 22:06:54
  • Re:此题很有问题.....用kruscal做的,不用sort就AC...加上sort就RE.... (10) caotong0 2010-08-02 22:07:17