#include<iostream>
using namespace std;
#define N 5000
struct edge
{int i,j;
int w;
};
int venum,ednum;
int sn[N];
int sn2[N];
void Adjust(edge *e,int s,int m)
{int j;
e[0]=e[s];
for(j=2*s;j<=m;j++){
if(j<m&&e[j].w>e[j+1].w)j++;
if(e[j].w>e[0].w)break;
e[s]=e[j];
s=j;
}
e[s]=e[0];
}
void initial(edge *e){
int i=1;
for(;i<=venum;i++){
sn[i]=-1;
sn2[i]=0;
}
for(i=ednum/2;i>0;i--)//*****************易错
Adjust(e,i,ednum);
}
edge find_me(edge *e,int &k)
{edge m=e[1];
e[1]=e[k];
e[k]=m;
k--;
if(k>1)
Adjust(e,1,k);
return m;

}
void find_re(int &i)
{int j=i;
while(sn[j]>0)
j=sn[j];
while(j!=i){
int t=sn[i];
sn[i]=j;//************易错 
i=t;
}
}
void set_min(int i,int j,int w)
{
     if(sn[i]<sn[j]){
     sn[i]=sn[i]+sn[j];
     sn[j]=i;
     sn2[j]=w;//a new idea
     }
     else {
     sn[j]=sn[i]+sn[j];
     sn[i]=j;
     sn2[2]=w;
     }
     
     }
bool find_same(edge *e,int tn,int w)
{
     for(int i=1;i<=venum;i++)
if(sn[i]==tn&&w==sn2[i])
return true;


return false;
}
bool K_mst(edge *e)
{int k=venum;
int k1=ednum;
int cost=0;
initial(e);
edge me;
while(k>0&&k1>0){
//venum-1 edges
 me=find_me(e,k1);
int i=me.i;
int j=me.j;
find_re(i);
find_re(j);
if(i!=j){      
set_min(i,j,me.w);
k--;
cost+=me.w;
}
else
if(find_same(e,i,me.w))
return true;
}
if(k1>0)
cout<<cost-me.w<<endl;
else
cout<<cost<<endl;
return false;
}
void creat(edge *e)
{cin>>venum>>ednum;
for(int i=1;i<=ednum;i++)
cin>>e[i].i>>e[i].j>>e[i].w;
}
int main()
{int t;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
cin>>t;
while(t--){
    edge e[N];
creat(e);
if(K_mst(e))
cout<<"Not Unique!"<<endl;
}
system("pause");
return 0;
}

• Re:求救呀，谁能提供些数据吗?（讨论中的数据都测过了，都没问题） (1775) 2209080118 2010-06-17 15:02:45