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

用邻接表吧~ Yen's improvement 加速

Posted by cuiaoxiang at 2008-09-30 23:38:35 on Problem 3680
In Reply To:这是我的建图 但是我TLE了 Posted by:20053565 at 2008-09-29 12:51:52
> void init()
> {
> 	int i;
> 
> 	scanf("%d%d", &N, &K);
> 	memset(net, 0, sizeof(net));
> 	num.clear();
> 	for (i = 0; i < N; i++)
> 	{
> 		scanf("%d%d%d", &itv[i].a, &itv[i].b, &itv[i].w);
> 		num.insert(itv[i].a);
> 		num.insert(itv[i].b);
> 	}
> 	int id = 1;
> 	for (set<int> ::iterator it = num.begin(); it != num.end(); ++it, ++id)
> 	{
> 		ID[*it] = id;
> 	}
> 	for (i = 0; i <= id; i++)
> 	{
> 		net[i][i+1].c = K;
> 		net[i][i+1].w = 0;
> 	}
> 	for (i = 0; i < N; i++)
> 	{
> 		net[ID[itv[i].a]][ID[itv[i].b]].c = 1;
> 		net[ID[itv[i].a]][ID[itv[i].b]].w = -itv[i].w;
> 		net[ID[itv[i].b]][ID[itv[i].a]].w = itv[i].w;
> 	}
> 	minc = 0;
> 	n = id + 2;
> 	s = 0;
> 	t = n - 1;
> }

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