{"id":145,"date":"2010-03-06T16:42:00","date_gmt":"2010-03-06T08:42:00","guid":{"rendered":"http:\/\/localhost\/?p=145"},"modified":"2010-03-06T16:42:00","modified_gmt":"2010-03-06T08:42:00","slug":"hnoi2006_highway_construction","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=145","title":{"rendered":"[HNOI2006]\u516c\u8def\u4fee\u5efa\u95ee\u9898"},"content":{"rendered":"

61.187.179.132:8080\/JudgeOnline\/showproblem<\/a>
\u770b\u4f3c\u6c34\u9898\u3002\u3002\u5176\u5b9e\u4e0d\u662f\u5f88\u6c34\uff08\u5e94\u8be5\u662f\u6211\u592a\u83dc\u4e86\u56e7\u3002\u3002\uff09
\u4e4b\u524d\u60f3\u4e86\u51e0\u79cd\u7b97\u6cd5\u90fd\u662f\u9519\u7684\u3002\u3002\u5c31\u4e0d\u8bf4\u4e86\u3002\u6700\u540e\u7684\u7b97\u6cd5\u662f\u4e8c\u5206\u6700\u5927\u503c\u3002\u5e76\u7528\u5e76\u67e5\u96c6\u5e2e\u5fd9(*^__^*)
\u7136\u540e\u9996\u5148\u626b\u63cf\u4e00\u904d\u6240\u6709\u7684\u8fb9\uff0c\u80fd\u591f\u5efa\u4e00\u53f7\u516c\u8def\u7684\u5c31\u5efa\u4e00\u53f7\u516c\u8def\u3002\u626b\u63cf\u7684\u8bdd\u5982\u679ck\u6ca1\u8fbe\u5230\uff0c\u5c31\u662ffalse
\u7136\u540e\u518d\u626b\u63cf\u4e00\u904d\u6240\u6709\u7684\u8fb9\uff0c\u628a\u80fd\u5efa\u7684\u4e8c\u53f7\u516c\u8def\u4e5f\u5efa\u4e0a\u53bb\u3002\u5224\u65ad\u4e00\u4e0b\u662f\u5426\u8054\u901a\u7684\u5c31OK\u4e86\u3002\u3002
Code\uff1a
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1;
const int maxn=10000;
int n,k,m;
struct Data
{
int s,t,c1,c2;
void operator()(int _s,int _t,int _c1,int _c2)
{s=_s;t=_t;c1=_c1;c2=_c2;}
}E[maxn*2];
int F[maxn];
int find(int x)
{
if(F[x]==x) return x;
return F[x]=find(F[x]);
}
int Union(int i,int j){F[j]=i;}
bool check(int limit)
{
int cnt=n,r=k;
rep(i,n) F[i]=i;
for(Data*i=E;i!=E+m;i++)
{
if(i->c2<=limit)
{
int a=find(i->s),b=find(i->t);
if(a!=b) Union(a,b),–cnt,–r;
}
}
if(r>0) return false;
for(Data*i=E;i!=E+m;i++)
{
if(i->c1<=limit)
{
int a=find(i->s),b=find(i->t);
if(a!=b) Union(a,b),–cnt;
}
if(cnt==1) return true;
}
return false;
}
int main()
{
\/\/freopen("in","r",stdin);
cin>>n>>k>>m;int s,t,c1,c2;
rep(i,m)
{
scanf("%d %d %d %d",&s,&t,&c2,&c1);
E[i](s-1,t-1,c1,c2);
}
int l=0,r=30000;
while(l+1<r)
{
int m=(l+r)\/2;
if(check(m))
r=m;
else
l=m;
}
cout<<r<<endl;
} <\/p>\n","protected":false},"excerpt":{"rendered":"

61.187.179.132:8080\/JudgeOnline\/showproblem\u770b\u4f3c\u6c34\u9898\u3002\u3002\u5176\u5b9e\u4e0d\u662f\u5f88\u6c34\uff08\u5e94\u8be5\u662f\u6211\u592a\u83dc\u4e86\u56e7\u3002\u3002\uff09\u4e4b\u524d\u60f3\u4e86\u51e0\u79cd\u7b97\u6cd5\u90fd\u662f\u9519\u7684\u3002\u3002\u5c31\u4e0d\u8bf4\u4e86\u3002\u6700\u540e\u7684\u7b97\u6cd5\u662f\u4e8c\u5206\u6700\u5927\u503c\u3002\u5e76\u7528\u5e76\u67e5\u96c6\u5e2e\u5fd9(*^__^*) \u7136\u540e\u9996\u5148\u626b\u63cf\u4e00\u904d\u6240\u6709\u7684\u8fb9\uff0c\u80fd\u591f\u5efa\u4e00\u53f7\u516c\u8def\u7684\u5c31\u5efa\u4e00\u53f7\u516c\u8def\u3002\u626b\u63cf\u7684\u8bdd\u5982\u679ck\u6ca1\u8fbe\u5230\uff0c\u5c31\u662ffalse\u7136\u540e\u518d\u626b\u63cf\u4e00\u904d\u6240\u6709\u7684\u8fb9\uff0c\u628a\u80fd\u5efa\u7684\u4e8c\u53f7\u516c\u8def\u4e5f\u5efa\u4e0a\u53bb\u3002\u5224\u65ad\u4e00\u4e0b\u662f\u5426\u8054\u901a\u7684\u5c31OK\u4e86\u3002\u3002Code\uff1a#include<cstdio>#include<iostream>#include<algorithm>#include<string>#include<vector>#include<cstring>#include<queue>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_backusing namespace std;const int inf=~0U>>1;const int maxn=10000;int n,k,m;struct Data{ int s,t,c1,c2; void operator()(int _s,int _t,int _c1,int _c2) {s=_s;t=_t;c1=_c1;c2=_c2;}}E[maxn*2];int F[maxn];int find(int x){ if(F[x]==x) return x; return F[x]=find(F[x]);}int Union(int i,int j){F[j]=i;}bool check(int limit){ int cnt=n,r=k; rep(i,n) F[i]=i; for(Data*i=E;i!=E+m;i++) { if(i->c2<=limit) { int a=find(i->s),b=find(i->t); if(a!=b) Union(a,b),–cnt,–r; } } if(r>0) return false; for(Data*i=E;i!=E+m;i++) […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/145"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=145"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/145\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=145"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=145"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=145"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}