Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:你给的数据没通过 还是ac了。。

Posted by 20145104009 at 2015-07-19 21:05:57 on Problem 1679 and last updated at 2015-07-19 21:26:55
In Reply To:Re:给后来人一组数据 Posted by:20145104009 at 2015-07-19 21:02:40
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct node 
{
	int a,b,cost;
}c[10005];
int fa[105],tree[105][105],vis[10005],vis_tree[105];
int n,m,max1;
bool cmp(node x,node y)
{
	if(x.cost<y.cost) 
	return true;
	else
	return false;
}
int find(int x)
{
	if(fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}
void sec_tree(int a,int b)
{
	vis_tree[a]=1;
	if(a==b)
	return ;
	for(int i=1;i<=n;i++)
	if(tree[a][i]&&!vis_tree[i])
	{
		if(max1<tree[a][i])
		max1=tree[a][i];
		sec_tree(i,b);
	}
}
int main()
{
	int ncase;
	scanf("%d",&ncase);
	while(ncase--)
	{
		memset(vis,0,sizeof(vis));
		memset(tree,0,sizeof(tree));
		memset(&c,0,sizeof(&c));
		scanf("%d %d",&n,&m);
		for(int i=1;i<=n;i++)
		fa[i]=i;
		for(int i=0;i<m;i++)
		scanf("%d %d %d",&c[i].a,&c[i].b,&c[i].cost);
		sort(c,c+m,cmp);
		int sum=0;
		for(int i=0;i<m;i++)
		{
			int x=find(c[i].a);
			int y=find(c[i].b);
			if(x!=y)
			{
				fa[x]=y,sum+=c[i].cost;
				tree[x][y]=tree[y][x]=c[i].cost;
				vis[i]=1;
			}
		}
		int flag=0;
		for(int i=0;i<m;i++)
		{
			if(!vis[i])
			{
				max1=-1;
                                memset(vis_tree,0,sizeof(vis_tree));
				sec_tree(c[i].a,c[i].b);
				if(max1==c[i].cost)
				{
					flag=1;
					break;
				}
			}
		}
		if(!flag)
		printf("%d\n",sum);
		else
		printf("Not Unique!\n");
	}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator