【洛谷 P1251】 餐巾计划问题 （费用流）

题目链接

我做的网络流24题里的第一题。。

想是不可能想到的，只能看题解。

首先，我们拆点，将一天拆成晚上和早上，每天晚上会受到脏餐巾（来源：当天早上用完的餐巾，在这道题中可理解为从原点获得），每天早上又有干净的餐巾（来源：购买、快洗店、慢洗店）。

1.从原点向每一天晚上连一条流量为当天所用餐巾x，费用为0的边，表示每天晚上从起点获得x条脏餐巾。

2.从每一天早上向汇点连一条流量为当天所用餐巾x，费用为0的边，每天白天,表示向汇点提供x条干净的餐巾,流满时表示第i天的餐巾够用 。

3.从每一天晚上向第二天晚上连一条流量为INF，费用为0的边，表示每天晚上可以将脏餐巾留到第二天晚上（注意不是早上，因为脏餐巾在早上不可以使用）。

4.从每一天晚上向这一天+快洗所用天数t1的那一天早上连一条流量为INF，费用为快洗所用钱数的边，表示每天晚上可以送去快洗部,在地i+t1天早上收到餐巾 。

5.同理，从每一天晚上向这一天+慢洗所用天数t2的那一天早上连一条流量为INF，费用为慢洗所用钱数的边，表示每天晚上可以送去慢洗部,在地i+t2天早上收到餐巾 。

6.从起点向每一天早上连一条流量为INF，费用为购买餐巾所用钱数的边，表示每天早上可以购买餐巾 。 注意，以上6点需要建反向边！3~6点需要做判断（即连向的边必须<=n）

(懒得写了)(摘自洛谷题解)

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

#define INF 2147483647

typedef long long ll;

const int MAXN = 4010;

const int MAXM = 40010;

queue <int> q;

int s, t, now, n, m;

struct Edge{

    int from, next, to, rest, cost;

}e[MAXM];

int head[MAXN], num = 1, vis[MAXN], Flow[MAXN], pre[MAXN];

ll dis[MAXN], mincost;

inline void Add(int from, int to, int flow, int cost){

    e[++num] = (Edge){ from, head[from], to, flow, cost }; head[from] = num;

    e[++num] = (Edge){ to, head[to], from, 0, -cost }; head[to] = num;

}

int RoadsExist(){

    q.push(s);

    memset(dis, 127, sizeof dis);

    dis[s] = 0; Flow[s] = INF; pre[t] = 0;

    while(!q.empty()){

		now = q.front(); q.pop(); vis[now] = 0;

		for(int i = head[now]; i; i = e[i].next)

			if(e[i].rest && dis[e[i].to] > dis[now] + e[i].cost){

				dis[e[i].to] = dis[now] + e[i].cost;

				pre[e[i].to] = i;

				Flow[e[i].to] = min(Flow[now], e[i].rest);

				if(!vis[e[i].to]){

					vis[e[i].to] = 1;

					q.push(e[i].to);

				}

			}

    }

    return pre[t];

}

int a[MAXN], buy, qw, qc, sw, sc;

int main(){

    scanf("%d", &n);

    for(int i = 1; i <= n; ++i)

       scanf("%d", &a[i]);

    scanf("%d%d%d%d%d", &buy, &qw, &qc, &sw, &sc);

    s = (n << 1) + 1; t = s + 1;

    for(int i = 1; i <= n; ++i){

		Add(s, i << 1, a[i], 0);

		Add((i << 1) - 1, t, a[i], 0);

		Add(s, (i << 1) - 1, INF, buy);

		if(i != n) Add(i << 1, (i + 1) << 1, INF, 0);

		if(i + qw <= n) Add(i << 1, ((i + qw) << 1) - 1, INF, qc);

		if(i + sw <= n) Add(i << 1, ((i + sw) << 1) - 1, INF, sc);

    }

    while(RoadsExist()){

		mincost += Flow[t] * dis[t];

		for(int i = t; i != s; i = e[pre[i]].from){

			e[pre[i]].rest -= Flow[t];

			e[pre[i] ^ 1].rest += Flow[t];

		}

    }

    printf("%lld\n", mincost);

    return 0;

}

【洛谷 P1251】 餐巾计划问题 （费用流）的相关教程结束。