2020-07-06 个人赛1 F:Milk Pumping
题面:
题解:其实方法很多,千万别浪到网络流用dinic求最大网络流求的最小费用,这题不一样。最大流/最小费用 不一定大于 流量/费用的最大值!
其实本题用邻接表存储,加上队列和结构体完全可以做本题,难度不高于bfs的裸题。
代码:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#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) << '
';
return 0;
}
总结:只要选取合理的存储方式,这类题目基本代码难度不高。