[HNOI2006]公路修建问题
期望20，实际10 没想到，居然在我的骗分代码上删了两个if后就A了，神奇？！！ 题目描述
分析
其实就是一个两次生成树，我考场上可能有一点问题居然想了kruskal+DP让后再想到了有限制的生成树等各种奇特的算法。因为看到必须要有k条生成树的边中是第一类，并且c1>=c2，所以直接先对c1进行排序，然后再对他求半棵生成树，一棵有k条边的生成树，然后再构成剩下n-k-1条边的半棵生成树，注意，此时的排序应该是c2的权值进行排序，应为此时构成的边是c2权值。让后就直接在求生成树的时候max一下，求一下最大的权值，让后输出，了事。
code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std
;
const int MAXN
= 2e4 + 5;
int n
,k
,m
,fa
[MAXN
];
struct node
{
int a
,b
,c1
,c2
;
}p
[MAXN
];
void Make_Set() {
for(int i
= 1;i
<= m
;i
++) fa
[i
] = i
;
}
int Find_Set(int x
) {
if(fa
[x
] == x
) return x
;
return fa
[x
] = Find_Set(fa
[x
]);
}
int Sum
;
bool cmp1(node x
,node y
){return x
.c2
< y
.c2
;}
bool cmp2(node x
,node y
){return x
.c1
< y
.c1
;}
void Kruskal() {
sort(p
+ 1,p
+ m
,cmp1
);
for(int i
= 1;i
< m
;i
++) {
int x
= Find_Set(p
[i
].a
),y
= Find_Set(p
[i
].b
);
if(x
== y
) continue;
fa
[x
] = y
;
Sum
= max(Sum
,p
[i
].c2
);
}
printf("%d",Sum
);
}
void kruskal() {
sort(p
+ 1,p
+ m
,cmp2
);
int q
= 0;
for(int i
= 1;i
< m
;i
++) {
int x
= Find_Set(p
[i
].a
);
int y
= Find_Set(p
[i
].b
);
if(x
== y
) continue;
fa
[x
] = y
;
Sum
= max(Sum
,p
[i
].c1
);
q
++;
if(q
== k
) break;
}
}
int main() {
scanf("%d %d %d",&n
,&k
,&m
);
for(int i
= 1;i
<= m
- 1;i
++)
scanf("%d %d %d %d",&p
[i
].a
,&p
[i
].b
,&p
[i
].c1
,&p
[i
].c2
);
Make_Set();
kruskal();
Kruskal();
return 0;
}
