Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
用邻接表吧~ Yen's improvement 加速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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator