NOip2016 模拟试题 复赛 提高组 day1
(road.cpp/c/pas)
【问题描述】
很久很久以前有一个国家，这个国家有N个城市，城市由1,2,3,…,N标号，城市间有M条双向道路，每条道路都有两个属性g和s，两个城市间可能有多条道路，并且可能存在将某一城市与其自身连接起来的道路。后来由于战争的原因，国王不得不下令减小花费从而关闭一些道路，但是必须要保证任意两个城市相互可达。
道路花费的计算公式为wG*max{所有剩下道路的属性g}+wS*max{所有剩下道路的属性s}，其中wG和wS是给定的值。国王想要在满足连通性的前提下使这个花费最小，现在需要你计算出这个花费。
【输入格式】
输入文件名为road.in。
第一行包含两个正整数N和M。第二行包含两个正整数wG和wS。
后面的M行每行描述一条道路，包含四个正整数u,v,g,s，分别表示道路连接的两个城市以及道路的两个属性。
【输出格式】
输出文件名为road.out。
输出一个整数，表示最小花费。若无论如何不能满足连通性，输出-1。
【输入输出样例】
road.in
3 3 2 1 1 2 10 15 1 2 4 20 1 3 5 1
road.out
30
【数据规模与约定】
对于10%的数据，N≤10，M≤20；对于30%的数据，N≤100，M≤1000；对于50%的数据，N≤200，M≤5000；
对于100%的数据，N≤400，M≤50000，wG,wS,g,s≤1000000000。
代码系转载
#include<iostream>#include<cstdio>#include<algorithm>using namespace std;typedef long long ll;const int MAXN=4e2,MAXM=5e4;const ll INF=1e17;int N,M,wS,wG;int cnt;int fa[MAXN+1];ll ans=INF;struct node{ int x,y;bool vis; ll g,s;} e[MAXM+1],tree[MAXM+1],tmp[MAXM+1];bool cmp(const node & a,const node & b){ if(a.g==b.g) return a.s<b.s; return a.g<b.g;}int find(int x){ if(fa[x]==x) return x; return fa[x]=find(fa[x]);}void small(ll maxg){ int i; for(i=1;i<=cnt;i++) tmp[i]=tree[i],tmp[i].vis=false; ll maxs=0,tot=0; for(i=1;i<=N;i++) fa[i]=i;//初始化并查集 for(i=1;i<=cnt;i++) { int a=find(tree[i].x),b=find(tree[i].y); if(a!=b) { maxs=max(maxs,tree[i].s); fa[a]=b; tot++; tmp[i].vis=true; } if(tot==N-1) { int p=0; for(i=1;i<=cnt;i++) if(tmp[i].vis) tree[++p]=tmp[i]; cnt=p; ans=min(ans,maxg+maxs); break; } }}int main(){ freopen("road.in","r",stdin); freopen("road.out","w",stdout); int i,j; cin>>N>>M>>wG>>wS; for(i=1;i<=M;i++) { scanf("%d%d%I64d%I64d",&e[i].x,&e[i].y,&e[i].g,&e[i].s); e[i].g*=(ll)wG,e[i].s*=(ll)wS; } sort(e+1,e+M+1,cmp); for(i=1;i<=M;i++)//遍历每条边 { if(e[i].g+e[i].s>ans) continue;//剪枝， //若现在的这条边的花费比之前算的ans还大就跳过 int pos=cnt+1; for(j=1;j<=cnt;j++) if(tree[j].s>e[i].s) { pos=j; break; } if(pos==cnt+1) tree[++cnt]=e[i]; else { for(j=++cnt;j>=pos+1;j--) tree[j]=tree[j-1]; tree[pos]=e[i]; } small(e[i].g); } if(ans==INF) cout<<-1<<endl; else cout<<ans<<endl; return 0;}新闻热点
疑难解答
