> 附代码:
> #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.... (10) caotong0 2010-08-02 22:07:17