[BZOJ 2654]tree
APIO的时候听了一下wqs二分，做了这题，然后现在才写题解……
wqs二分的思路大抵就是你要求必须选\(k\)个，那就二分每个操作的一个“额外代价”，然后进行没有限制的选择。然后最后选出来的个数事和你二分的代价正相关/反相关的。
这道题的话，就二分选择黑边的代价，然后跑一般的最小生成树（有相同边权时要选择黑边！）。当然我们会遇到一个问题，就是二分到\(x\)的时候选的比\(k\)多，到\(x + 1\)的时候又比\(k\)少了。这道题的处理方法，事考虑代价为\(x\)时，其实存在选\(k\)个的最优解（如果说大于\(x\)那就没了），因此我们钦点代价为\(x\)跑一遍限制只能选\(k\)条黑边的最短路即可。
代码：
/**************************************************************
Problem: 2654
User: danihao123
Language: C++
Result: Accepted
Time:5756 ms
Memory:5856 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
const int maxn = 50005;
const int maxm = 100005;
struct Edge {
int u, v, d;
int typ;
bool operator <(const Edge &res) const {
if(d == res.d) {
return typ < res.typ;
} else {
return d < res.d;
}
}
};
Edge E[maxm];
int n, m, need;
int par[maxn], siz[maxn];
void init_dsu() {
for(int i = 1; i <= n; i ++) {
par[i] = i;
siz[i] = 1;
}
}
int get_fa(int x) {
if(par[x] == x) {
return x;
} else {
return (par[x] = get_fa(par[x]));
}
}
void link_set(int x, int y) {
if(siz[x] > siz[y]) std::swap(x, y);
siz[y] += siz[x];
par[x] = y;
}
void merge_set(int x, int y) {
return link_set(get_fa(x), get_fa(y));
}
bool is_same(int x, int y) {
return (get_fa(x) == get_fa(y));
}
typedef long long ll;
int ans = 0x7fffffff;
bool kruskal(int delta) {
std::vector<Edge> vec;
for(int i = 1; i <= m; i ++) {
Edge e = E[i];
if(e.typ == 0) {
e.d += delta;
}
vec.push_back(e);
}
std::sort(vec.begin(), vec.end());
int used = 0; ll tot = -(ll(delta)) * (ll(need));
init_dsu();
for(int i = 0; i < m; i ++) {
const Edge &e = vec[i];
int u = e.u, v = e.v;
if(!is_same(u, v)) {
if(used == need && e.typ == 0) continue;
merge_set(u, v); tot += e.d;
if(e.typ == 0) used ++;
}
}
if(used == need) {
ans = std::min(ans, (int(tot)));
return true;
} else {
return false;
}
}
int main() {
scanf("%d%d%d", &n, &m, &need);
for(int i = 1; i <= m; i ++) {
scanf("%d%d%d%d", &E[i].u, &E[i].v, &E[i].d, &E[i].typ);
E[i].u ++; E[i].v ++;
}
int L = -10000001, R = 10000001;
while(true) {
#ifdef LOCAL
printf("Range (%d, %d)\n", L, R);
fflush(stdout);
#endif
if(R - L <= 3) {
for(int i = R; i >= L; i --) {
if(kruskal(i)) {
break;
}
}
break;
}
int M = L + (R - L) / 2;
if(kruskal(M)) {
L = M;
} else {
R = M;
}
}
printf("%d\n", ans);
return 0;
}
[SZKOpuł ben][AMPPZ2014]Petrol
aji波兰题！（迫真）
啊波兰题真好康（一转）
考虑怎么去除非加油站的影响……对于每两个加油站，取他们的最短路，然后建出来一个图，这个图的MST上的路径的走法就事最优走法。
但这样显然会凉……因为\(s\)肥肠巨大，会T。然后我们考虑多源最短路，并且给每个点标记到它最近的加油站（称为来源）。那么考虑两条加油站间的路径，上面一定有一条边满足边两个端点不一样（证明考虑……如果所有边两边端点的来源都一样，那么所有边的来源会同时事那两个加油站）。
然后一个小问题事，如果一个点有多个来源，只考虑一个会出事吗？这个事不会的。比如说有三个加油站\(a\)、\(b\)、\(c\)，如果说三者到一个点的最短路都一样，那么我们考虑只取\(a\)。如果\(b\)和\(c\)本来能连一条边，但现在因为这个连不了了，那他们还是能同时各和\(a\)连一条长度和原来的那条边长度一样的边，所以事实上没有什么笋丝。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
const int maxn = 200005, maxm = 400005;
int first[maxn];
int next[maxm], to[maxm], dist[maxm];
bool dir[maxm];
void add_edge(int u, int v, int w, bool d = true) {
static int cnt = 0;
cnt ++; next[cnt] = first[u]; first[u] = cnt;
to[cnt] = v; dist[cnt] = w; dir[cnt] = d;
}
void ins_edge(int u, int v, int w) {
add_edge(u, v, w); add_edge(v, u, w, false);
}
using ll = long long;
using pii = std::pair<ll, int>;
int n; std::vector<int> V;
ll d[maxn]; int src[maxn];
bool vis[maxn];
void dij() {
memset(d, 0x1f, sizeof(d));
std::priority_queue<pii, std::vector<pii>, std::greater<pii> > Q;
for(auto p : V) {
d[p] = 0; src[p] = p;
Q.push(std::make_pair(0LL, p));
}
while(!Q.empty()) {
int u = Q.top().second; Q.pop();
if(vis[u]) continue;
vis[u] = true;
for(int i = first[u]; i; i = next[i]) {
int v = to[i];
if(d[u] + (ll(dist[i])) < d[v]) {
d[v] = d[u] + (ll(dist[i]));
src[v] = src[u];
Q.push(std::make_pair(d[v], v));
}
}
}
}
int p[maxn], rk[maxn];
int get_fa(int x) {
if(p[x] == x) {
return x;
} else {
return (p[x] = get_fa(p[x]));
}
}
void link_set(int x, int y) {
if(rk[x] > rk[y]) std::swap(x, y);
p[x] = y;
if(rk[x] == rk[y]) rk[y] ++;
}
void merge_set(int x, int y) {
x = get_fa(x); y = get_fa(y);
if(x != y) link_set(x, y);
}
bool is_same(int x, int y) {
return (get_fa(x) == get_fa(y));
}
void init_set() {
for(int i = 1; i <= n; i ++) {
p[i] = i;
}
}
struct Edge {
int u, v; ll w;
Edge(int a = 0, int b = 0, ll c = 0) {
u = a; v = b; w = c;
}
bool operator <(const Edge &res) const {
return w < res.w;
}
};
int m; Edge E[maxm];
int ecnt;
void process() {
dij(); ecnt = 0;
for(int i = 1; i <= n; i ++) {
for(int j = first[i]; j; j = next[j]) {
int v = to[j];
if(dir[j] && src[i] != src[v]) {
E[++ ecnt] = Edge(src[i], src[v], (ll(dist[j])) + d[i] + d[v]);
}
}
}
std::sort(E + 1, E + 1 + ecnt);
}
bool ans[maxm];
void solve() {
int q; scanf("%d", &q);
init_set(); int cur = 0;
std::vector<std::pair<Edge, int> > Q;
for(int i = 1; i <= q; i ++) {
int u, v; ll w; scanf("%d%d%lld", &u, &v, &w);
Q.push_back(std::make_pair(Edge(u, v, w), i));
}
std::sort(Q.begin(), Q.end());
for(auto x : Q) {
Edge e = x.first;
while(cur < ecnt && E[cur + 1].w <= e.w) {
cur ++;
merge_set(E[cur].u, E[cur].v);
}
ans[x.second] = is_same(e.u, e.v);
}
for(int i = 1; i <= q; i ++) {
if(ans[i]) {
puts("TAK");
} else {
puts("NIE");
}
}
}
int main() {
int s; scanf("%d%d%d", &n, &s, &m);
for(int i = 1; i <= s; i ++) {
int x; scanf("%d", &x);
V.push_back(x);
}
for(int i = 1; i <= m; i ++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
ins_edge(u, v, w);
}
process(); solve();
return 0;
}
[POJ 2784]Buy or Build
啊这题竟然在POJ上有……
枚举套餐子集是肯定的啦，但接下来呢？有的同学或许会想直接Kruskal求MST。但是估计会T。
有一个很有效的优化：先求一遍不加套餐的MST，然后接下来每次求MST的时候都只考虑这[tex]n-1[/tex]条边，这样就很快了。
需要注意的是，这[tex]n-1[/tex]以外的边就算加入了套餐也不会被考虑。因为无论加不加套餐，这些更大的边所能连接的连通分量总是可以被以前更小的边连接，所以这条边无论如何也不会被考虑啦……
代码写起来容易让人崩溃……所以说这个题很能锻炼代码能力和Debug能力。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=1005,maxq=8;
int n;
int p[maxn],rank[maxn];
int find_set(int x){
if(p[x]==x)
return x;
else
return p[x]=find_set(p[x]);
}
inline void link_set(int x,int y){
if(rank[x]>rank[y]){
p[y]=x;
}else{
p[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
inline void union_set(int x,int y){
link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
return find_set(x)==find_set(y);
}
inline void init_set(){
register int i;
for(i=1;i<=n;i++)
p[i]=i;
memset(rank,0,sizeof(rank));
}
int Cost[maxq];
vector<int> V[maxq];
struct Edge{
int u,v,d;
bool operator <(const Edge& x) const{
return d<x.d;
}
};
vector<Edge> bj;
vector<Edge> E;
vector<Edge> garbage;
int MST(int cnt,vector<Edge>& E,vector<Edge>& to){
if(!cnt)
return 0;
register int i,ans=0;
to.clear();
for(i=0;i<E.size();i++){
if(!is_same(E[i].u,E[i].v)){
union_set(E[i].u,E[i].v);
ans+=E[i].d;
to.push_back(E[i]);
if(!(--cnt))
break;
}
}
return ans;
}
int zb[maxn][2];
inline int EucSqr(int x,int y){
int t1=zb[x][0]-zb[y][0],t2=zb[x][1]-zb[y][1];
t1*=t1;
t2*=t2;
return t1+t2;
}
int main(){
int T,q,num,u;
register int i,j,k,cnt,temp,ans;
scanf("%d%d",&n,&q);
for(i=0;i<q;i++){
scanf("%d%d",&num,&Cost[i]);
V[i].clear();
while(num--){
scanf("%d",&u);
V[i].push_back(u);
}
}
for(i=1;i<=n;i++){
scanf("%d%d",&zb[i][0],&zb[i][1]);
}
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++){
bj.push_back((Edge){i,j,EucSqr(i,j)});
}
init_set();
sort(bj.begin(),bj.end());
ans=MST(n-1,bj,E);
for(i=0;i<(1<<q);i++){
init_set();
temp=0;
cnt=n-1;
for(j=0;j<q;j++)
if(i&(1<<j)){
temp+=Cost[j];
for(k=1;k<V[j].size();k++){
if(!is_same(V[j][k],V[j][0])){
union_set(V[j][k],V[j][0]);
cnt--;
}
}
}
ans=min(ans,temp+MST(cnt,E,garbage));
}
printf("%d\n",ans);
return 0;
}
[POJ 1679]The Unique MST
又是一个上百行代码的题……
这个题要求判断MST的唯一性。我们可以通过求非严格的次小生成树，来判断MST的唯一性。
非严格的次小生成树就是枚举考虑将MST外的哪条边加入替换MST中的一条边。替换的方法是，求出MST中待加入边两端路径上最大边，删掉之后再把待加入边加进去。假如有一个非严格次小生成树权值和和MST一样，就说明MST不唯一。
代码：
#include <cstdio>
#include <cstring>
#include <bitset>
#include <algorithm>
using namespace std;
const int maxn=105,maxm=10005;
#define REP(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define CL_ARR(x,v) memset(x,v,sizeof(x))
int first[maxn];
int next[205],to[205],dist[205];
int graph_cnt=0;
inline void AddEdge(int u,int v,int d){
graph_cnt++;
next[graph_cnt]=first[u];
first[u]=graph_cnt;
to[graph_cnt]=v;
dist[graph_cnt]=d;
}
inline void ClearGraph(){
CL_ARR(first,0);
CL_ARR(next,0);
CL_ARR(to,0);
CL_ARR(dist,0);
graph_cnt=0;
}
int anc[maxn][32],maxcost[maxn][32];
int dep[maxn];
void dfs(int x,int depth,int fa,int d){
int i;
dep[x]=depth;
anc[x][0]=fa;
maxcost[x][0]=d;
GRAPH_REP(i,x){
if(to[i]!=fa){
dfs(to[i],depth+1,x,dist[i]);
}
}
}
int n;
inline void process(){
register int i,j,a;
dfs(1,0,0,0);
for(j=1;(1<<j)<n;j++){
REP(i,n){
if(anc[i][j-1]!=-1){
a=anc[i][j-1];
anc[i][j]=anc[a][j-1];
maxcost[i][j]=max(maxcost[i][j-1],maxcost[a][j-1]);
}
}
}
}
int query(int x,int y){
register int tmp,log,i,ans=-0x7fffffff;
if(dep[x]<dep[y])
swap(x,y);
for(log=1;(1<<log)<=dep[x];log++);
log--;
for(i=log;i>=0;i--)
if(dep[x]-(1<<log)>=dep[y]){
ans=max(ans,maxcost[x][i]);
x=anc[x][i];
}
if(x==y)
return ans;
for(i=log;i>=0;i--)
if(anc[x][i]!=-1 && anc[x][i]!=anc[y][i]){
ans=max(ans,maxcost[x][i]);
x=anc[x][i];
ans=max(ans,maxcost[y][i]);
y=anc[y][i];
}
ans=max(ans,maxcost[x][0]);
ans=max(ans,maxcost[y][0]);
return ans;
}
int p[maxn],rank[maxn];
int find_set(int x){
if(p[x]==x)
return x;
else
return p[x]=find_set(p[x]);
}
void link_set(int x,int y){
if(rank[x]>rank[y]){
p[y]=x;
}else{
p[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
inline void union_set(int x,int y){
link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
return find_set(x)==find_set(y);
}
inline void init_set(){
register int i;
REP(i,n)
p[i]=i;
CL_ARR(rank,0);
}
struct Edge{
int u,v,d;
bool operator <(const Edge& x) const{
return d<x.d;
}
};
#define ALL_FT(x) E[x].u,E[x].v
Edge E[maxm];
int m;
bitset<maxn> Choose;
int MST(){
register int i,ans=0,cnt=0;
ClearGraph();
init_set();
Choose.reset();
sort(E+1,E+1+m);
REP(i,m){
if(!is_same(ALL_FT(i))){
Choose[i]=true;
cnt++;
ans+=E[i].d;
union_set(ALL_FT(i));
AddEdge(ALL_FT(i),E[i].d);
AddEdge(E[i].v,E[i].u,E[i].d);
}
if(cnt==(n-1)){
break;
}
}
return ans;
}
int main(){
int T;
int u,v,d;
register int i,ans,temp;
bool OK;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
REP(i,m){
scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d);
}
ans=MST();
CL_ARR(anc,-1);
process();
OK=true;
REP(i,m){
if(!Choose[i]){
temp=query(ALL_FT(i));
if(temp==E[i].d){
OK=false;
puts("Not Unique!");
break;
}
}
}
if(OK)
printf("%d\n",ans);
}
return 0;
}
[BZOJ 1196]公路修建问题
挺简单的二分答案题……然而到现在才A
思路很明显，直接二分最终答案。那么判定如何做呢？
假设判定谓词为[tex]C(x)[/tex]，那么我们首先考虑选白边。贪心加入边权小于[tex]x[/tex]的边（当然是否有必要就要用并查集判定了。并且这样就算加的超过了[tex]k[/tex]条也不会对答案造成影响）。然后白边加的不够[tex]k[/tex]谓词就是假了。
然后再考虑黑边，接下来的事情就很简单了。
代码：
/**************************************************************
Problem: 1196
User: danihao123
Language: C++
Result: Accepted
Time:672 ms
Memory:1212 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=0;i<(n);i++)
#define RAP(i,n) for(i=1;i<=(n);i++)
const int maxn=10001,maxm=20001;
struct Edge{
int u,v,d1,d2;
};
bool cmp1(const Edge& x,const Edge& y){
return x.d1<y.d1;
}
bool cmp2(const Edge& x,const Edge& y){
return x.d2<y.d2;
}
int n;
int p[maxn],rank[maxn];
int find_set(int x){
if(p[x]==x)
return x;
else
return p[x]=find_set(p[x]);
}
inline void link_set(int x,int y){
if(rank[x]>rank[y]){
p[y]=x;
}else{
p[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
inline void union_set(int x,int y){
link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
return find_set(x)==find_set(y);
}
inline void init_set(){
register int i;
for(i=1;i<=n;i++)
p[i]=i;
memset(rank,0,sizeof(rank));
}
int k,m;
Edge E[maxm];
inline bool check(int x){
register int i,first_cnt=0,cnt=0;
init_set();
sort(E,E+m,cmp1);
REP(i,m){
if(E[i].d1>x){
break;
}else{
if(!is_same(E[i].u,E[i].v)){
first_cnt++;
cnt++;
union_set(E[i].u,E[i].v);
}
}
if(cnt==n-1){
return true;
}
}
if(first_cnt<k)
return false;
sort(E,E+m,cmp2);
REP(i,m){
if(E[i].d2>x){
break;
}else{
if(!is_same(E[i].u,E[i].v)){
cnt++;
union_set(E[i].u,E[i].v);
}
}
if(cnt==n-1)
return true;
}
return false;
}
int main(){
register int i,L=1,M,R=0;
scanf("%d%d%d",&n,&k,&m);
m--;
REP(i,m){
scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].d1,&E[i].d2);
R=max(R,E[i].d1);
}
R++;
while(L<R){
M=L+(R-L)/2;
if(check(M))
R=M;
else
L=M+1;
}
printf("%d\n",L);
return 0;
}
[BZOJ 1682]干草危机
这道题就是求最小瓶颈生成树中边的最大值。
然而图的MST就是图的一个最小瓶颈生成树……这下问题就迎刃而解了。
代码：
/**************************************************************
Problem: 1682
User: danihao123
Language: C++
Result: Accepted
Time:44 ms
Memory:940 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=0;i<n;i++)
#define REPB(i,n) for(i=1;i<=n;i++)
#define FROMG_TO E[i].u,E[i].v
const int maxn=2001,maxm=10001;
int n,m;
// Djoint set
int p[maxn],rank[maxn];
int find_set(int x){
if(p[x]==x)
return x;
else
return p[x]=find_set(p[x]);
}
void link_set(int x,int y){
if(rank[x]>rank[y]){
p[y]=x;
}else{
p[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
inline void union_set(int x,int y){
link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
return find_set(x)==find_set(y);
}
inline void init_set(){
register int i;
for(i=1;i<=n;i++)
p[i]=i;
// memset(rank,0,sizeof(rank));
}
// Graph
struct Edge{
int u,v,d;
};
int cmp(const Edge& a,const Edge& b){
return a.d<b.d;
}
Edge E[maxm];
int mst(){
register int i,cnt=0,ans=0;
init_set();
sort(E,E+m,cmp);
for(i=0;cnt<(n-1) && i<m;i++){
if(!is_same(FROMG_TO)){
union_set(FROMG_TO);
ans=max(ans,E[i].d);
cnt++;
}
}
return ans;
}
int main(){
register int i;
scanf("%d%d",&n,&m);
REP(i,m){
scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d);
}
printf("%d\n",mst());
return 0;
}
[BZOJ 1601]灌水
一定有人问我我死哪里去了……
这题挺简单的，但是对于zzs这种图论渣来讲，是巨大的困难……
这题可以造一个虚拟结点，所有点和它连该点点权长的边，其他边的正常造，然后剩下MST的就很简单了……
然而第一次写Prim……哎
代码：
[洛谷 P1967]货车运输
倍增LCA经典题……
这题的做法就是求最大生成树，然后用倍增LCA法求瓶颈路……
注意一下，两点不连通时输出-1（其实这个用并查集判断不就行了……）！！！
代码：
