NOip2016 模擬試題 復(fù)賽 提高組 day1
(road.cpp/c/pas)
【問題描述】
很久很久以前有一個國家，這個國家有N個城市，城市由1,2,3,…,N標(biāo)號，城市間有M條雙向道路，每條道路都有兩個屬性g和s，兩個城市間可能有多條道路，并且可能存在將某一城市與其自身連接起來的道路。后來由于戰(zhàn)爭的原因，國王不得不下令減小花費(fèi)從而關(guān)閉一些道路，但是必須要保證任意兩個城市相互可達(dá)。
道路花費(fèi)的計算公式為wG*max{所有剩下道路的屬性g}+wS*max{所有剩下道路的屬性s}，其中wG和wS是給定的值。國王想要在滿足連通性的前提下使這個花費(fèi)最小，現(xiàn)在需要你計算出這個花費(fèi)。
【輸入格式】
輸入文件名為road.in。
第一行包含兩個正整數(shù)N和M。第二行包含兩個正整數(shù)wG和wS。
后面的M行每行描述一條道路，包含四個正整數(shù)u,v,g,s，分別表示道路連接的兩個城市以及道路的兩個屬性。
【輸出格式】
輸出文件名為road.out。
輸出一個整數(shù)，表示最小花費(fèi)。若無論如何不能滿足連通性，輸出-1。
【輸入輸出樣例】
road.in
3 3 2 1 1 2 10 15 1 2 4 20 1 3 5 1
road.out
30
【數(shù)據(jù)規(guī)模與約定】
對于10%的數(shù)據(jù)，N≤10，M≤20；對于30%的數(shù)據(jù)，N≤100，M≤1000；對于50%的數(shù)據(jù)，N≤200，M≤5000；
對于100%的數(shù)據(jù)，N≤400，M≤50000，wG,wS,g,s≤1000000000。
代碼系轉(zhuǎn)載
#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;//剪枝， //若現(xiàn)在的這條邊的花費(fèi)比之前算的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;}新聞熱點(diǎn)
疑難解答
