題目描述
OI island是一個非常漂亮的島嶼,自開發以來,到這兒來旅游的人很多，然而，由于該島嶼剛剛開發不久，所以那
里的交通情況還是很糟糕，所以，OIER Association組織成立了，旨在建立OI island的交通系統， OI island有n
個旅游景點，不妨將它們從1到n標號，現在，OIER Association需要修公路將這些景點連接起來，一條公路連接兩
個景點，公路有，不妨稱它們為一級公路和二級公路，一級公路上的車速快，但是修路的花費要大一些， OIER As
sociation打算修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的花費，
輸出格式
一個資料，表示花費最大的公路的花費，
樣例
樣例輸入
10 4 20
3 9 6 3
1 3 4 1
5 3 10 2
8 9 8 7
6 8 8 3
7 1 3 2
4 9 9 5
10 8 9 1
2 6 9 1
6 7 9 8
2 6 2 1
3 8 9 5
3 2 9 6
1 6 10 3
5 6 3 1
2 7 6 1
7 8 6 2
10 9 2 1
7 1 10 2
樣例輸出
5
題目分析
首先看完題，我們會發現，這道題要求一個最小生成樹，基本就是一個克魯斯卡爾的板題，但是，仔細一看，會發現，有倆個邊權，第一個邊權必須要達到K，而第二個比第一個小，沒有限制
很明顯，要先給第一個排序，然后，就連K條邊，這樣，就解決了K個一級路
然后，可以把第二個排序，排完后，連剩下的邊，然后，在執行時，求連的邊最大值，然后，不就是道板題嗎
注意，邊要開兩倍
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int ans=0;
int x,y,c1,c2,u1,v1;
int fa[10005];
int jl;
struct edge{
int u,v,val1,val2;
}e[20005];
int find(int x)
{
if(fa[x]==x)
{
return x;
}
else
{
fa[x]=find(fa[x]);
return fa[x];
}
}
bool cmp(edge x,edge y)
{
if(x.val1==y.val1)
{
return x.val2>y.val2;
}
else
{
return x.val1<y.val1;
}
}
bool kmp(edge x,edge y)
{
return x.val2<y.val2;
}
int main()
{
scanf("%d %d%d",&n,&k,&m);
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
for(int i=1;i<m;i++)
{
scanf("%d %d%d %d",&x,&y,&c1,&c2);
e[i].u=x;
e[i].v=y;
e[i].val1=c1;
e[i].val2=c2;
}
int tot=0;
sort(e+1,e+m,cmp);
for(int i=1;i<m;i++)
{
int u=e[i].u;
int v=e[i].v;
int val=e[i].val1;
if(find(u)!=find(v))
{
fa[find(u)]=find(v);
if(ans<val)
{
ans=val;
}
tot++;
}
if(tot==k)
{
break;
}
}
sort(e+1,e+m,kmp);
for(int i=1;i<m;i++)
{
int u=e[i].u;
int v=e[i].v;
int val=e[i].val2;
if(find(u)!=find(v))
{
fa[find(u)]=find(v);
if(ans<val)
{
ans=val;
}
tot++;
}
if(tot==n)
{
break;
}
}
printf("%d",ans);
return 0;
}
跪求二分解法（詳解）
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/163462.html
標籤：其他
上一篇：CTF 內涵的軟體 stage1
下一篇：golang入門系列之Go GC