Milk Pumping

ZJNU-huyh 2020-07-06 原文

今天第一次正式打个人定位赛，还是太菜，这题连枚举加最短路都没想到，显然菜是原罪。

题面：

：

题解：其实方法很多，千万别浪到网络流用dinic求最大网络流求的最小费用，这题不一样。最大流/最小费用不一定大于流量/费用的最大值！

其实本题用邻接表存储，加上队列和结构体完全可以做本题，难度不高于bfs的裸题。

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string.h>
#include <cstring>
#include <map>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
struct node {
    int price;
    int flow;
    double rate;
    node() {}
    node(int cc, int ff) { price = cc; flow = ff; }
}p[1005];
struct gd {
    int e;//终点
    int price;
    int flow;
    gd() {}
    gd(int ee, int pp, int ff) { e = ee; price = pp; flow = ff; }
};
vector<gd>Map[1005];
int main(void)
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        Map[a].push_back(gd(b, c, d));
        Map[b].push_back(gd(a, c, d));
    }
    p[1].price = 0; p[1].flow = inf; p[1].rate = 0;
    for (int i = 2; i <= n; i++)
    {
        p[i].price = inf;
        p[i].flow = 0;
        p[i].rate = 0;
    }
    queue<int>q;
    q.push(1);
    int df, dc; 
    double dr;
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        for (int i = 0; i < Map[now].size(); i++)
        {
            df = min(Map[now][i].flow, p[now].flow);//此时的管道流量=min（新管道流量，当前点位的流量最小值）
            dc = p[now].price + Map[now][i].price;//新价格=当前点位不安放这根管道的总价+这根管道的价格
            dr = 1.0 * df / dc;
            if (dr > p[Map[now][i].e].rate)//如果通过这根管道到达下一个点位，能比之前已经存储的下一个点位的最高占比更加高的话，选取这根管道，并且更新数据
            {
                p[Map[now][i].e].flow = df;
                p[Map[now][i].e].price = dc;
                p[Map[now][i].e].rate = dr;
                q.push(Map[now][i].e);
            }
        }
    }
    cout << (floor)(1000000LL * p[n].rate) << '\n';
    return 0;
}