# [BZOJ2245]&&[SDOI2011] 工作安排

2 3
2 2 2
1 1 0
0 0 1
1
2
1 10
1
2
1 6

## 样例输出 SampleOutput

24

BZOJ 2245

long long 的速度不忍直视。。。

``````#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
const int inf = 0x7fffffff / 27.11;
const int maxn = 505;
const int maxm = maxn * maxn;
int i, j, t, n, m, l, r, k, z, y, x;
struct edge
{
int to, fl, co, nx;
} e[maxm];
int c[maxn], a[maxn];
int cnt, num, s;
deque <int> q;
inline void ins(int u, int v, int f, int c)
{
e[cnt] = (edge)
{
};
e[cnt] = (edge)
{
};
}
inline bool spfa(int s, int t, int tim)
{
int i, u, v, w;
while (!q.empty()) q.pop_front();
for (i = s; i <= t; i++) dis[i] = inf;
dis[s] = 0; used[s] = tim; pre[s] = -1;
q.push_back(s);
while (!q.empty())
{
u = q.front(); q.pop_front(); used[u] = 0;
for (i = head[u]; i != -1; i = e[i].nx)
{
v = e[i].to; w = e[i].co;
if (dis[v] > dis[u] + w && e[i].fl > 0)
{
dis[v] = dis[u] + w;
pre[v] = i;
if (used[v] != tim)
{
used[v] = tim;
if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
else q.push_back(v);
}
}
}
}
return (dis[t] != inf);
}
inline void mcmf(int s, int t)
{
int i, f;
ll ans = 0;
while (spfa(s, t, ++num))
{
for (f = inf, i = pre[t]; i != -1; i = pre[e[i ^ 1].to]) f = min(f, e[i].fl);
for (i = pre[t]; i != -1; i = pre[e[i ^ 1].to]) e[i].fl -= f, e[i ^ 1].fl += f;
ans += f * dis[t];
}
printf("%lld\n", ans);
}
int main()
{
cnt = num = 0;
scanf("%d%d", &m, &n);
for (i = 1; i <= n; i++) scanf("%d", &x), ins(0, i, x, 0);
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
{
scanf("%d", &x);
if (x == 1) ins(j, n + i, inf, 0);
}
for (i = 1; i <= m; i++)
{
scanf("%d", &s);
for (j = 1; j <= s; j++) scanf("%d", &a[j]); a[s + 1] = inf;
for (j = 1; j <= s + 1; j++) scanf("%d", &x), ins(n + i, n + m + 1, a[j] - a[j - 1], x);
}
mcmf(0, m + n + 1);
return 0;
}``````