题面

题解

如果没有分段函数的限制的话就很好做了

但是我们发现分段函数的段很少,我们就可以将每一段拆开,

强制限制一定流量就可以了

代码

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<algorithm>
#include<queue>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define clear(x, y) memset(x, y, sizeof(x)) inline int read()
{
int data = 0, w = 1; char ch = getchar();
while(ch != '-' && (!isdigit(ch))) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();
return data * w;
} const int maxn(1010), maxm(500010);
struct edge { int next, to, cap, dis; } e[maxm];
int head[maxn], e_num = -1, n, S, T, m;
int pre[maxn], pre_e[maxn], vis[maxn];
long long cost, flow, dis[maxn], h[maxn];
int g[300][300], t[11], c[11]; inline void add_edge(int from, int to, int cap, int dis)
{
e[++e_num] = (edge) {head[from], to, cap, dis}; head[from] = e_num;
e[++e_num] = (edge) {head[to], from, 0, -dis}; head[to] = e_num;
} std::queue<int> q;
void MinCostMaxFlow()
{
std::fill(h + S, h + T + 1, 0);
cost = flow = 0; int f = 1000000007;
while(f)
{
std::fill(dis + S, dis + T + 1, LLONG_MAX >> 1); clear(vis, 0);
dis[S] = 0, q.push(S);
while(!q.empty())
{
int x = q.front(); q.pop();
for(RG int i = head[x]; ~i; i = e[i].next)
{
int to = e[i].to, ds = e[i].dis + dis[x] + h[x] - h[to];
if(e[i].cap > 0 && ds < dis[to])
{
dis[to] = ds, pre[to] = x, pre_e[to] = i;
if(!vis[to]) vis[to] = 1, q.push(to);
}
}
vis[x] = 0;
}
if(dis[T] == LLONG_MAX >> 1) return;
for(RG int i = S; i <= T; i++) h[i] += dis[i];
int cap = f;
for(RG int i = T; i ^ S; i = pre[i])
cap = std::min(cap, e[pre_e[i]].cap);
f -= cap, flow += cap, cost += cap * h[T];
for(RG int i = T; i ^ S; i = pre[i])
e[pre_e[i]].cap -= cap, e[pre_e[i] ^ 1].cap += cap;
}
} int main()
{
clear(head, -1); n = read(), m = read(); S = 0, T = n + m + 1;
for(RG int i = 1; i <= m; i++)
add_edge(i + n, n + m + 1, read(), 0);
for(RG int i = 1; i <= n; i++)
for(RG int j = 1; j <= m; j++)
g[i][j] = read();
for(RG int i = 1, x; i <= n; i++)
{
x = read();
for(RG int j = 1; j <= x; j++) t[j] = read();
for(RG int j = 1; j <= x + 1; j++) c[j] = read();
for(RG int j = 1; j <= x; j++)
add_edge(0, i, t[j] - t[j - 1], c[j]);
add_edge(0, i, 1000000007, c[x + 1]);
for(RG int j = 1; j <= m; j++)
if(g[i][j]) add_edge(i, j + n, 1000000007, 0);
}
MinCostMaxFlow();
printf("%lld\n", cost);
return 0;
}

最新文章

  1. JavaScript (If...Else和Switch和循环遍历) 语句以及常用消息框
  2. tyvj1198 最优矩阵连乘
  3. 前端学PHP之基础语法
  4. Linux下部署solrCloud
  5. 【C++】运算符重载
  6. Miniprofiler在普通net项目中的使用
  7. sr4000自带API和opencv结合获取图像
  8. new的例子
  9. nyoj 1100 WAJUEJI which home strong!
  10. [学习笔记]设计模式之Adapter
  11. DateDiff 函数,用生日获得年龄
  12. 使用Ant自动化发布web工程
  13. [转] linux中cat more less head tail 命令
  14. Windbg调试命令详解(1)
  15. trove,测试,db小解析
  16. ArcGIS API for JavaScript 中的数据类型【vs】GPServer的数据类型
  17. 两个input均分自适应
  18. user-agent | what is the &quot;user-agent&quot; ?
  19. 【php】 php获取文件路径中的文件名和文件后缀方法
  20. html 表格边线设置

热门文章

  1. JDBC连接数据库
  2. js判断地址转向
  3. 一句jQuery代码返回顶部
  4. 如何在IamgeButton上面添加文字
  5. chrome 优秀的插件推荐
  6. (引用)web安全测试
  7. iOS 数据类型
  8. HW7.3
  9. servlet 容器,工作原理,优缺点
  10. InfoPath本地发布及部署
  11. JavaScript自动关闭窗口
  12. cdn与http缓存
  13. SharePoint Secure Store Service(SSSS)的使用(一)
  14. XShell删除键之类的不正常
  15. 《JAVA与模式》之工厂方法模式
  16. shell脚本学习之实例列举
  17. 高性能迷你React框架anujs1.1.0发布
  18. 【字符串算法3】浅谈KMP算法
  19. nltk模块基础操作
  20. passwd: Have exhausted maximum number of retries for service