【并查集&&带权并查集】BZOJ3296&&POJ1182

bzoj1529[POI2005]ska Piggy banks【题目大意】n头奶牛m种语言,每种奶牛分别掌握一些语言。问至少再让奶牛多学多少种语言,才能使得它们能够直接或间接交流?【思路】(n+m)个点,奶牛学会某种语言就合并它和语言的节点。并查集维护联通块,答案为联通块个数-1。水,可是我跳坑了
9次阅读

poj 3255 Roadblocks

Roadblocks Time Limit: 2000MS  Memory Limit: 65536K Total Submissions: 13216  Accepted: 4660 DescriptionBessie has m
12次阅读

【二分查找-最大化平均值】POJ2976 - Dropping Test

【题目大意】给出n组ai和bi,去掉k个使得a的总和除以b的总和最大。【思路】也就是取(n-k)个数,最大化平均值,见《挑战程序设计竞赛》P144,最后公式为c(x)=((ai-x*bi)从大到小排列的前(n-k)个的和不小于0)。 1 #include<iostream> 2 #inc
8次阅读

POJ 3259 Wormholes (判负环)

WormholesTime Limit: 2000MS Memory Limit: 65536KTotal Submissions: 46123 Accepted: 17033DescriptionWhile exploring his many farms,
7次阅读

【最大化平均值】POJ3111-K Best

【题目大意】给出v[]和w[],求的最大值。【思路】二分s(S)的值,可变形为s(S)*Σw>=Σv,所以只需要把求出x*w[i]-v[i],看看前k个的和是否大于等于0,大于等于0就满足条件。由于进度非常高,注意二分的写法。*原本在check(mid)=1之后会存下ansqueue,然后再输
7次阅读

poj1190

生日蛋糕Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 18230 Accepted: 6491Description 7月17日是Mr.W的生日,ACM-THU为此要制作一个体积为Nπ
7次阅读

[POJ3252]Round Numbers

[POJ3252]Round Numbers试题描述The cows, as you know, have no fingers or thumbs and thus are unable to play Scissors, Paper, Stone' (also known as 'Rock, P
5次阅读

[POJ&HDU]杂题记录

POJ2152树形dp,每次先dfs一遍求出距离再枚举所有点转移即可。#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>
20次阅读

poj 2449 Remmarguts' Date k短路

/*poj 2449 k短路 A* 估价函数是 s到i的距离+i到t的距离 */#include<cstdio>#include<queue>#include<vector>#define inf 1e7#define maxn 100010using names
5次阅读

poj 3463 最短路与次短路的方案数求解

SightseeingTime Limit: 2000MS Memory Limit: 65536KTotal Submissions: 8968 Accepted: 3139DescriptionTour operator Your Personal Holiday organ
4次阅读