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的花費，
輸出描述:
一個資料，表示花費最大的公路的花費，
示例1
輸入
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
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N=10001,M=20001,K=10001;
struct edge
{
int from,to,dis,nex;
}e[2*N],ee[2*N];
int head[N],cnt1,cnt2;
void add(edge *e,int u,int v,int w,int &tot)
{
e[++tot].to=v;
e[tot].from=u;
e[tot].dis=w;
e[tot].nex=head[u];
head[u]=tot;
}
int f[N];
int find(int x)
{
return f[x]==x ? x : f[x]=find(f[x]);
}
bool cmp(edge a,edge b)
{
if(a.dis!=b.dis)return a.dis<b.dis;
return a.from<b.from;
}
int sum,ans;
void kruskal(edge *e,int m,int k)
{
sum=0;
for(int i=1;i<=m;++i)
{
int x=e[i].from,y=e[i].to,fx=find(x),fy=find(y);
if(fx!=fy)
{
f[fx]=fy;
++sum;
ans=max(ans,e[i].dis);
}
if(sum==k)return;
}
}
int n ,k , m;
int main()
{
n = read();k = read();m = read();
for(int i=1;i<=n;++i)f[i]=i;
for(int i=1;i<m;++i)
{
int a=read(),b=read(),c=read(),d=read();
add(e,a,b,d,cnt1);add(ee,a,b,c,cnt2);
}
sort(ee+1,ee+1+cnt2,cmp);
kruskal(ee,cnt2,k);
sort(e+1,e+1+cnt1,cmp);
kruskal(e,cnt1,n-1-k);
cout<<ans;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/266001.html
標籤：其他
上一篇：STM32CubeMX學習筆記（15）——電源管理(PWR)低功耗睡眠模式
下一篇：ESP8266連接ONENET