[luoguP1251] 餐巾计划问题（费用流）

传送门

模型

网络优化问题，用最小费用最大流解决。

实现

把每天分为二分图两个集合中的顶点Xi,Yi，建立附加源S汇T。

1、从S向每个Xi连一条容量为ri，费用为0的有向边。

2、从每个Yi向T连一条容量为ri，费用为0的有向边。

3、从S向每个Yi连一条容量为无穷大，费用为p的有向边。

4、从每个Xi向Xi+1(i+1<=N)连一条容量为无穷大，费用为0的有向边。

5、从每个Xi向Yi+m(i+m<=N)连一条容量为无穷大，费用为f的有向边。

6、从每个Xi向Yi+n(i+n<=N)连一条容量为无穷大，费用为s的有向边。

求网络最小费用最大流，费用流值就是要求的最小总花费。

分析

这个问题的主要约束条件是每天的餐巾够用，而餐巾的来源可能是最新购买，也可能是前几天送洗，今天刚刚洗好的餐巾。每天用完的餐巾可以选择送到快洗部或慢洗部，或者留到下一天再处理。

经过分析可以把每天要用的和用完的分离开处理，建模后就是二分图。二分图X集合中顶点Xi表示第i天用完的餐巾，其数量为ri，所以从S向Xi连接容量为ri的边作为限制。Y集合中每个点Yi则是第i天需要的餐巾，数量为ri，与T连接的边容量作为限制。每天用完的餐巾可以选择留到下一天（Xi->Xi+1），不需要花费，送到快洗部(Xi->Yi+m)，费用为f，送到慢洗部(Xi->Yi+n)，费用为s。每天需要的餐巾除了刚刚洗好的餐巾，还可能是新购买的(S->Yi)，费用为p。

在网络上求出的最小费用最大流，满足了问题的约束条件（因为在这个图上最大流一定可以使与T连接的边全部满流，其他边只要有可行流就满足条件），而且还可以保证总费用最小，就是我们的优化目标。

还是得好好理解这个建图。

然而这个代码在洛谷上超时了，不会zkw费用流QAQ

——代码

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #define N 4010

 #define M 100005

 #define INF ~(1 << 31)

 #define min(x, y) ((x) < (y) ? (x) : (y))

 int a, p, m, f, n, g, s, t, cnt;

 int head[N], to[M], val[M], cost[M], next[M], dis[N], pre[N];

 bool vis[N];

 long long sum;

 inline int read()

 {

     int x = , f = ;

     char ch = getchar();

     for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;

     for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';

     return x * f;

 }

 inline void add(int x, int y, int z, int c)

 {

     to[cnt] = y;

     val[cnt] = z;

     cost[cnt] = c;

     next[cnt] = head[x];

     head[x] = cnt++;

 }

 inline bool spfa()

 {

     int i, u, v;

     std::queue <int> q;

     memset(vis, , sizeof(vis));

     memset(pre, -, sizeof(pre));

     memset(dis,  / , sizeof(dis));

     q.push(s);

     dis[s] = ;

     while(!q.empty())

     {

         u = q.front(), q.pop();

         vis[u] = ;

         for(i = head[u]; i ^ -; i = next[i])

         {

             v = to[i];

             if(val[i] && dis[v] > dis[u] + cost[i])

             {

                 dis[v] = dis[u] + cost[i];

                 pre[v] = i;

                 if(!vis[v])

                 {

                     q.push(v);

                     vis[v] = ;

                 }

             }

         }

     }

     return pre[t] ^ -;

 }

 int main()

 {

     int i, x, d;

     a = read();

     s = , t = (a << ) + ;

     memset(head, -, sizeof(head));

     for(i = ; i <= a; i++)

     {

         x = read();

         add(s, i, x, ), add(i, s, , );

         add(i + a, t, x, ), add(t, i + a, , );

     }

     p = read();

     m = read();

     f = read();

     n = read();

     g = read();

     for(i = a + ; i <= a + a; i++) add(s, i, INF, p), add(i, s, , -p);

     for(i = ; i < a; i++) add(i, i + , INF, ), add(i + , i, , );

     for(i = ; i <= a - m; i++) add(i, i + a + m, INF, f), add(i + a + m, i, , -f);

     for(i = ; i <= a - n; i++) add(i, i + a + n, INF, g), add(i + a + n, i, , -g);

     while(spfa())

     {

         d = 1e9;

         for(i = pre[t]; i ^ -; i = pre[to[i ^ ]]) d = min(d, val[i]);

         for(i = pre[t]; i ^ -; i = pre[to[i ^ ]])

         {

             val[i] -= d;

             val[i ^ ] += d;

         }

         sum += (long long)dis[t] * d;

     }

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

     return ;

 }

巴特西

[luoguP1251] 餐巾计划问题（费用流）

最新文章

热门文章