洛谷 P5837 [USACO19DEC]Milk Pumping G (单源最短路,dijkstra)

洛谷 P5837 [USACO19DEC]Milk Pumping G   (单源最短路,dijkstra)

  • 题意:有一\(n\)个点,\(m\)条边的双向图,每条边都有花费和流量,求从\(1\)~\(n\)的路径中,求\(max\frac{min(f)}{\sum c}\).

  • 题解:对于c,一定是单源最短路,我们可以用dijkstra,但是这个最小流量不是很好搞,但是题目所给的数据范围较小,所以我们可以直接枚举最小流量,然后每次初始化数组跑dijkstra,去找大于当前最小流量的边,如果\(1\)~\(n\)有路径能走,我们每次维护答案的最小值.

  • 代码:

    struct misaka{
    int out;
    int val;
    int flow;
    }p; int n,m;
    int dis[N];
    bool st[N];
    vector<misaka> v[N]; void dijkstra(int x){
    for(int i=1;i<=n;++i){
    dis[i]=INF;
    st[i]=false;
    }
    dis[1]=0;
    priority_queue<PII,vector<PII>,greater<PII>> h;
    h.push({0,1}); while(!h.empty()){
    auto tmp=h.top();
    h.pop(); int num=tmp.se;
    int dist=tmp.fi;
    if(st[num]) continue;
    st[num]=true;
    for(auto w:v[num]){
    if(x>w.flow) continue;
    int j=w.out;
    if(dist+w.val<dis[j]){
    dis[j]=dist+w.val;
    h.push({dis[j],j});
    }
    }
    }
    } int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;++i){
    int a,b;
    cin>>a>>b;
    cin>>p.val>>p.flow;
    p.out=b;
    v[a].pb(p);
    p.out=a;
    v[b].pb(p);
    }
    int ans=0;
    for(int i=1;i<=1000;++i){
    dijkstra(i);
    if(dis[n]!=INF) ans=max(ans,i*1000000/dis[n]);
    } cout<<ans<<endl; return 0;
    }
上一篇:UVA 11374 Airport Express SPFA||dijkstra


下一篇:Poj OpenJudge 百练 1062 昂贵的聘礼