HNOI2006公路修建问题
https://www.luogu.org/problemnew/show/P2323
【题目描述】
OI island是一个非常漂亮的岛屿,自开发以来,到这儿来旅游的人很多。然而,由于该岛屿刚刚开发不久,所以那里的交通情况还是很糟糕。所以,OIER Association组织成立了,旨在建立OI island的交通系统。 OI island有n个旅游景点,不妨将它们从1到n标号。现在,OIER Association需要修公路将这些景点连接起来。一条公路连接两个景点。公路有,不妨称它们为一级公路和二级公路。一级公路上的车速快,但是修路的花费要大一些。 OIER Association打算修n-1条公路将这些景点连接起来(使得任意两个景点之间都会有一条路径)。为了保证公路系统的效率, OIER Association希望在这n-1条公路之中,至少有k条(0≤k≤n-1)一级公路。OIER Association也不希望为一条公路花费的钱。所以,他们希望在满足上述条件的情况下,花费最多的一条公路的花费尽可能的少。而你的任务就是,在给定一些可能修建的公路的情况下,选择n-1条公路,满足上面的条件。
【输入输出格式】
- 输入格式
第一行有三个数n(1≤n≤10000),k(0≤k≤n-1),m(n-1≤m≤20000),这些数之间用空格分开。 N和k如前所述,m表示有m对景点之间可以修公路。以下的m-1行,每一行有4个正整数a,b,c1,c2 (1≤a,b≤n,a≠b,1≤c2≤c1≤30000)表示在景点a与b 之间可以修公路,如果修一级公路,则需要c1的花费,如果修二级公路,则需要c2的花费。
注意,在实际评测时,将只会有 m−1m-1m−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
本题是一道半裸的模板题,可以有两种做法,看到关键字“最大的最小值”,可以考虑使用二分答案,本篇博客主要讲解第二种方法——最小生成树。
首先将一级公路和二级公路分别排序,然后从小到大选k条边加入生成树,剩下的边在二级公路中选择。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define maxn 20010 using namespace std; int n,m,k,f[],vis[maxn][]; struct road
{
int u,v,w,tim;
}e1[maxn],e2[maxn]; int max(int x,int y)
{
return x<y?y:x;
} int getf(int node)
{
if(node==f[node])
return node;
f[node]=getf(f[node]);
return f[node];
} void meg(int x,int y)
{
int t1=getf(x),t2=getf(y);
if(t1==t2)
return;
f[t2]=t1;
} void qsort(int l,int r,int flag)
{
int i=l,j=r;
if(flag==) {
road mid=e1[(l+r)/];
do
{
while(e1[i].w<mid.w) i++;
while(e1[j].w>mid.w) j--;
if(i<=j)
{
road t=e1[i];
e1[i]=e1[j];
e1[j]=t;
i++;j--;
}
}while(i<=j);
}
else
{
road mid=e2[(l+r)/];
do
{
while(e2[i].w<mid.w) i++;
while(e2[j].w>mid.w) j--;
if(i<=j)
{
road t=e2[i];
e2[i]=e2[j];
e2[j]=t;
i++;j--;
}
}while(i<=j);
}
if(l<j) qsort(l,j,flag);
if(i<r) qsort(i,r,flag);
} int main()
{
scanf("%d%d%d",&n,&k,&m);
for(int i=;i<m;i++)
{
int x,y,c1,c2;
scanf("%d%d%d%d",&x,&y,&c1,&c2);
e1[i].u=x;e1[i].v=y;e1[i].tim=i;e2[i]=e1[i];
e1[i].w=c1;e2[i].w=c2;
}
qsort(,m-,);
qsort(,m-,);
for(int i=;i<=n;i++)
f[i]=i;
int num=,ans=-;
for(int i=;i<=k;i++)
{
while(getf(e1[num].u)==getf(e1[num].v))
num++;
meg(e1[num].u,e1[num].v);
vis[e1[num].tim][]=;
ans=max(e1[num].w,ans);
}
num=;
for(int i=k+;i<n;i++)
{
while(getf(e2[num].u)==getf(e2[num].v))
num++;
meg(e2[num].u,e2[num].v);
vis[e2[num].tim][]=;
ans=max(e2[num].w,ans);
}
printf("%d\n",ans);
for(int i=;i<m;i++)
{
if(vis[i][])
printf("%d 1\n",i);
else if(vis[i][])
printf("%d 2\n",i);
}
return ;
}
最新文章
- 【原】Spark之机器学习(Python版)(一)——聚类
- Python for Infomatics 第14章 数据库和SQL应用二(译)
- DOM example
- 我在 CSDN 的小窝
- eclipse-搭建maven的war项目集合spring注解方式
- C++全局和静态变量初始化
- C++简单单例模式
- ACM第四站————最小生成树(普里姆算法)
- struts2中修改Action后刷新浏览器后不能及时更新
- 判断包含字符String.contains
- GEF-whole-upload教程中遇到的问题及解决方案
- rollout
- MyBatis入门一
- 在使用Qt5.8完成程序动态语言切换时遇到的问题
- Notepad++ 的函数参数提示错误的问题终于解决了
- MyEclipse和eclipse生成变量快捷键
- 《Java并发编程的艺术》并发编程的挑战(一)
- Guid的生成和数据修整(去除空格和小写字符)
- shell-awk详细笔记
- blfs(systemd版本)学习笔记-安装lrzsz软件包实现ssh远程传输文件到lfs系统