#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct Edge
{
	int u,v,w;
	void scan()
	  {
	    scanf("%d%d%d",&u,&v,&w);
	  }
};
Edge edges[500001];
int ljb[201][201],en;
int T,n,m,fa[201],rank[201],tot,sum,maxcost[201][201];
int map[201][201],delta;
bool vis[201],used[201],hav[201];
void init()
{
	memset(rank,0,sizeof(rank));
	for(int i=1;i<=n;i++)
	  fa[i]=i;
}
int rt;
int findroot(int x)
{
	if(fa[x]==x)
	  return fa[x];
	rt=findroot(fa[x]);
	fa[x]=rt;
	return rt;
}
void Union(int f1,int f2)
{
	if(rank[f1]<rank[f2])
	  fa[f1]=f2;
	else
	  {
	  	fa[f2]=f1;
	  	if(rank[f1]==rank[f2])
	  	  rank[f1]++;
	  }
}
bool cmp(const Edge &a,const Edge &b)
{
	return a.w<b.w;
}
void dfs(int cur,int father)
{
	vis[cur]=hav[cur]=true;
	for(int i=1;i<=n;i++)
	  if(hav[i]&&i!=cur)
	    maxcost[i][cur]=maxcost[cur][i]=max(maxcost[i][father],map[cur][father]);
	for(int i=1;i<=ljb[cur][0];i++)
	  if(!vis[ljb[cur][i]])
	    dfs(ljb[cur][i],cur);
	vis[cur]=false;
}
int main()
{
	scanf("%d",&T);
	for(int zu=1;zu<=T;zu++)
	  {
	  	en=tot=sum=0;
	  	delta=2147483647;
	  	memset(ljb,0,sizeof(ljb));
	  	memset(maxcost,0,sizeof(maxcost));
	  	memset(hav,false,sizeof(hav));
	  	memset(vis,false,sizeof(vis));
	  	memset(map,0,sizeof(map));
	  	memset(used,false,sizeof(used));
	  	scanf("%d%d",&n,&m);
	  	for(int i=1;i<=m;i++)
	  	  edges[i].scan();
	  	sort(edges+1,edges+1+m,cmp);
	  	init();
	  	for(int i=1;i<=m;i++)
	  	  {
	  	  	int F1=findroot(edges[i].u),F2=findroot(edges[i].v);
	  	  	if(F1!=F2)
	  	  	  {
	  	  	  	Union(F1,F2);
	  	  	  	ljb[edges[i].u][++ljb[edges[i].u][0]]=edges[i].v;
	  	  	  	used[i]=true;
	  	  	  	ljb[edges[i].v][++ljb[edges[i].v][0]]=edges[i].u;
	  	  	  	map[edges[i].u][edges[i].v]=map[edges[i].v][edges[i].u]=edges[i].w;
	  	  	  	sum+=edges[i].w;
	  	  	  	tot++;
	  	  	  	if(tot==n-1)
	  	  	  	  break;
	  	  	  }
	  	  }
	  	dfs(edges[1].u,0);
	  	for(int i=1;i<=m;i++)
	  	  if(!used[i])
	  	    delta=min(delta,edges[i].w-maxcost[edges[i].u][edges[i].v]);
	  	if(delta<=0)
	  	  printf("Not Unique!\n");
	  	else
	  	  printf("%d\n",sum);
	  }
	return 0;
}

• Re:c++ 选手一定要用G++提交！！！！！！！！！！！！！否则会wa！<---血的教训（附代码，最小瓶颈路，n²）（绝对没有不连通图） (1599) zxtregister 2016-08-04 16:16:43