题解 P2323 【[HNOI2006]公路修建问题】
Drinkkk
·
·
题解
【参考资料】
liusu201601的博客：https://blog.csdn.net/liusu201601
【题目描述】
OI island是一个非常漂亮的岛屿，自开发以来，到这儿来旅游的人很多。然而，由于该岛屿刚刚开发不久，所以那里的交通情况还是很糟糕。所以，OIER Association组织成立了，旨在建立OI island的交通系统。
OI island有n个旅游景点，不妨将它们从1到n标号。现在，OIER Association需要修公路将这些景点连接起来。一条公路连接两个景点。公路有两种类型，不妨称它们为一级公路和二级公路。一级公路上的车速快，但是修路的花费要大一些。
OIER Association打算修n-1条公路将这些景点连接起来（使得任意两个景点之间都会有一条路径）。为了保证公路系统的效率, OIER Association希望在这n-1条公路之中,至少有k(0 \leq k \leq n-1)条一级公路。OIER Association也不希望为一条公路花费太多的钱。所以，他们希望在满足上述条件的情况下，花费最多的一条公路的花费尽可能的少。而你的任务就是，在给定一些可能修建的公路的情况下，选择n-1条公路，满足上面的条件。
【输入输出格式】
第一行有三个数n(1 \leq n \leq 10000),k(0 \leq k \leq n-1),m(n-1 \leq m \leq 20000)，这些数之间用空格分开。
以下的$m-1$行，每一行有$4$个正整数$a,b,c1,c2(1 \leq a,b \leq n,a \not= b,1 \leq c2 \leq c1 \leq 30000)$。
表示在景点$a$与$b$之间可以修公路，如果修一级公路，则需要$c1$的花费，如果修二级公路，则需要$c2$的花费。
**注意，在实际评测时，将只会有$m-1$条公路。**
- 输出格式
输出的第一行有一个数据，表示花费最大的公路的花费。
接下来的$n-1$行，每行有两个正整数$t$和$p$，$t$和$p$表示在输入的第$t$对（按照输入的顺序，从1开始标号）景点之间修建$p$级公路。
$n-1$条公路的输出必选$t$的大小递增，如果有多个方案使花费最大的公路花费最小，那么输出任意一个都可以。
【输入输出样例】
- 输入样例
```
4 2 5
1 2 6 5
1 3 3 1
2 3 9 4
2 4 6 1
```
- 输出样例
```
6
1 1
2 1
4 2
```
感谢@lutaiye dalao提出的建议，已修改样例。
【题解】
- 我会搜索！
考虑直接搜索判断用那一条边，代码实现难度不高，但时间复杂度过高，期望得分$0$~$35$分。
- 我会最小生成树！
我们可以先选$k$条高价路，$c1$小的边优先选（在这里我使用了$px1()$函数来进行排序）。由于考虑到$m \leq 20000$，所以我们在排序的时候要用快排。选完了这$k$条高价路后我们还要选$(n-1)-k$条低价路，由于$c2 \leq c1$，也即高价路一定比低价路要贵，所以选择低价路一定是最优的，在这里我们还要排一次快排，$c2$小的边优先选择（在这里我使用了$px2()$函数来进行排序），在选编的时候要将方案存到数组$fa[][]$里面去。在这里我用了$fa[][0]$来表示$t$，并且我用了$fa[][1]$来表示$p$，在这里我用了$f[i].su$来表示排序后的第$i$条边的输入的编号是多少。最后再按$t$的大小来排下序即可（在这里我用了函数$px3()$来实现这一部分）。由于我是用手写快排的，所以我的代码可能会长一些。下面上快排的部分（$px1()$和$px2()$以及$px3()$），以及最小生成树的部分（$kruskal()$，在这里我用$kruskal(1)$来表示选择那$k$条高价路的部分，并用$kruskal(2)$来表示选择那$(n-1)-k$条低价路的部分，并且我用了一个变量$ans$来记录答案，也即花费最多的那条公路的花费最小是多少）。还有要注意的是，如果在排$c1$的时候有相同的，那么$c2$大的优先。因为如果有边的$c1$的权值相同的话，那么肯定是留下那个$c2$小的边，因为这样子会更加的优哦。
下面上AC代码~
```
#include <cstdio>
struct node{ int x,y,c1,c2,su; } e[1000001];
int len=0,ans=0,n=0,m=0,k=0;
int fa[10001][2],f[10001];
int max(int x,int y)
{
return x>y?x:y;
}
void px1(int l,int r)
{
int x=l,y=r,mid=e[(l+r)/2].c1,t=e[(l+r)/2].c2;
while(x<=y)
{
while(e[x].c1<mid || (e[x].c1==mid && e[x].c2>t))
{
x++;
}
while(e[y].c1>mid || (e[y].c1==mid && e[y].c2<t))
{
y--;
}
if(x<=y)
{
node t=e[x];
e[x]=e[y];
e[y]=t;
x++;
y--;
}
}
if(l<y)
{
px1(l,y);
}
if(x<r)
{
px1(x,r);
}
}
void px2(int l,int r)
{
int x=l,y=r,mid=e[(l+r)/2].c2;
while(x<=y)
{
while(e[x].c2<mid)
{
x++;
}
while(e[y].c2>mid)
{
y--;
}
if(x<=y)
{
node t=e[x];
e[x]=e[y];
e[y]=t;
x++;
y--;
}
}
if(l<y)
{
px2(l,y);
}
if(x<r)
{
px2(x,r);
}
}
int find(int x)
{
if(x==f[x])
{
return x;
}
else
{
return f[x]=find(f[x]);
}
}
void kruskal(int x)
{
if(x==1)
{
int p=0;
for(int i=1;i<=m;i++)
{
int tx=find(e[i].x);
int ty=find(e[i].y);
if(tx!=ty)
{
f[tx]=ty;
fa[++len][0]=e[i].su;
fa[len][1]=1;
ans=max(ans,e[i].c1);
p++;
if(p==k)
{
break;
}
}
}
}
else if(x==2)
{
int p=k;
for(int i=1;i<=m;i++)
{
int tx=find(e[i].x);
int ty=find(e[i].y);
if(tx!=ty)
{
f[tx]=ty;
fa[++len][0]=e[i].su;
fa[len][1]=2;
ans=max(ans,e[i].c2);
p++;
if(p==n-1)
{
break;
}
}
}
}
}
void px3(int l,int r)
{
int x=l,y=r,mid=fa[(l+r)/2][0];
while(x<=y)
{
while(fa[x][0]<mid)
{
x++;
}
while(fa[y][0]>mid)
{
y--;
}
if(x<=y)
{
int t=fa[x][0];
fa[x][0]=fa[y][0];
fa[y][0]=t;
t=fa[x][1];
fa[x][1]=fa[y][1];
fa[y][1]=t;
x++;
y--;
}
}
if(l<y)
{
px3(l,y);
}
if(x<r)
{
px3(x,r);
}
}
int main()
{
scanf("%d %d %d",&n,&k,&m);
m--;
for(int i=1;i<=m;i++)
{
e[i].su=i;
scanf("%d %d %d %d",&e[i].x,&e[i].y,&e[i].c1,&e[i].c2);
}
for(int i=1;i<=n;i++)
{
f[i]=i;
}
px1(1,m);
kruskal(1);
px2(1,m);
kruskal(2);
printf("%d\n",ans);
px3(1,len);
for(int i=1;i<=len;i++)
{
printf("%d %d\n",fa[i][0],fa[i][1]);
}
return 0;
}
```