题解 P5837 【[USACO19DEC]Milk Pumping】

这题其实想法挺简单的，因为他只需要简单的把每个点的花费和流量用dp记下来就好了

1.怎么记：

首先考虑dp的状态。由于所在的点和流量都要记，所以dp开二维，一维记所在的点，另一维记去哪

//dp[i][j] ==> i 是现在所在的点，j是流量

2.从哪开始

看题

3.转移方法

//dp[要去的点][现在的流量和要去的流量的最小值] = dp[现在的点][现在的流量]+去的花费

4.输出

在终点，对于每个能到达的流量，最大值就是花费/流量

dijkstra代码：

#include <iostream>

#include <algorithm>

#include <math.h>

#include <cstring>

#include <queue>

#include <fstream>

using namespace std;

#define pp pair<long long,long long>

#define mp make_pair

long long maxi = 0, n,m, tot=0,head[100001];

struct Edge{

  long long to, next,cost,flow;

}edge[100001];

void add(long long x, long long y,long long co, long long fl){

  edge[tot].to = y;

  edge[tot].cost = co;

  edge[tot].flow = fl;

  edge[tot].next = head[x];

  head[x] = tot;

}

long long dp[1001][1001];

void dij(long long a, long long b){ // dijkstra

  dp[a][b] = 0;

  queue<pp> q;

  q.push(mp(a,b));

  while(!q.empty()){

    long long qf = q.front().first;

    long long qs = q.front().second;

    q.pop();

    for(long long i=head[qf];i;i=edge[i].next){

      long long t = edge[i].to, flo = edge[i].flow;

      if (dp[t][min(qs,flo)]>dp[qf][qs]+edge[i].cost){

        dp[t][min(qs,flo)] = dp[qf][qs]+edge[i].cost; //上面讲的转移

        q.push(mp(t,min(qs,flo)));

      }

    }

  }

}

int main(){

  // setIO("pump");

  cin >> n >> m;

  for (long long i=0;i<m;i++){

    long long a,b,c,d; cin >> a >> b >> c >> d; add(a,a,c,d); add(b,b,c,d);

  }

  memset(dp,0x3f3f3f3f,sizeof(dp));

  dij(1,1000);

  for (long long i=1;i<1000;i++){

    if (dp[n][i]>1e9) continue; //越界不？

    long long num = floor((double)(i*1e6)/(double)dp[n][i]); // 不越界计算

    maxi = max(maxi,num);

  }

  cout << maxi;

}

spfa:

#include <iostream>

#include <algorithm>

#include <math.h>

#include <cstring>

#include <queue>

#include <fstream>

using namespace std;

#define pp pair<long long,long long>

#define mp make_pair

long long maxi = 0, n,m, tot=0,head[100001];

struct Edge{

  long long to, next,cost,flow;

}edge[100001];

void add(long long x, long long y,long long co, long long fl){

  edge[tot].to = y;

  edge[tot].cost = co;

  edge[tot].flow = fl;

  edge[tot].next = head[x];

  head[x] = tot;

}

bool vis[1001][1001];

long long dp[1001][1001];

void spfa(long long a, long long b){

  dp[a][b] = 0;

  vis[a][b] = true;

  queue<pp> q;

  q.push(mp(a,b));

  while(!q.empty()){

    long long qf = q.front().first;

    long long qs = q.front().second;

    vis[qf][qs] = false;

    q.pop();

    for(long long i=head[qf];i;i=edge[i].next){

      long long t = edge[i].to, flo = edge[i].flow;

      if (dp[t][min(qs,flo)]>dp[qf][qs]+edge[i].cost){

        dp[t][min(qs,flo)] = dp[qf][qs]+edge[i].cost;

        if (!vis[t][min(qs,flo)]) {vis[t][min(qs,flo)] = true;q.push(mp(t,min(qs,flo)));}

      }

    }

  }

}

int main(){

  // setIO("pump");

  cin >> n >> m;

  for (long long i=0;i<m;i++){

    long long a,b,c,d; cin >> a >> b >> c >> d; add(a,a,c,d); add(b,b,c,d);

  }

  memset(dp,0x3f3f3f3f,sizeof(dp));

  spfa(1,1000);

  for (long long i=1;i<1000;i++){

    if (dp[n][i]>1e9) continue;

    long long num = floor((double)(i*1e6)/(double)dp[n][i]);

    maxi = max(maxi,num);

  }

  cout << maxi;

}

巴特西

题解 P5837 【[USACO19DEC]Milk Pumping】

最新文章

热门文章