学步园

 http://hzaskywalker.blog.163.com/blog/static/20379815720123291371918/

 zkw费用流模版

/************************************************************** 
    Problem: 2245 
    User: neko13 
    Language: C++ 
    Result: Accepted 
    Time:560 ms 
    Memory:5384 kb 
****************************************************************/
  
/* 
 * @author neko13 
 */
#include<iostream> 
#include<string> 
#include<cstdio> 
#include<cstring> 
using namespace std; 
#define A(i)  (i) 
#define B(i) ((i)+n) 
// 13C 
#define DBG 0 
#define sz(c) ((int)(c).size()) 
#define   forl(i, a, b) for(int i = (a); i <  (b); ++i) 
#define  forle(i, a, b) for(int i = (a); i <= (b); ++i) 
#define   forg(i, a, b) for(int i = (a); i >  (b); --i) 
#define  forge(i, a, b) for(int i = (a); i >= (b); --i) 
#define  forlc(i, a, b) for(int i##_b = (b), i = (a); i <  i##_b; ++i) 
#define forlec(i, a, b) for(int i##_b = (b), i = (a); i <= i##_b; ++i) 
#define  forgc(i, a, b) for(int i##_b = (b), i = (a); i >  i##_b; --i) 
#define forgec(i, a, b) for(int i##_b = (b), i = (a); i >= i##_b; --i) 
#define forall(i, v   ) forlc(i, 0,   sz(v)) 
#define forlla(i, v   ) forge(i, sz(v)-1, 0) 
#define  forls(i, n, a, b) for(int i = a; i != b; i = n[i]) 
#define rep(n)  for(int               repp = 0; repp <    (n); ++repp) 
#define repc(n) for(int repp_b = (n), repp = 0; repp < repp_b; ++repp) 
#define rst(a, v) memset(a, v, sizeof a) 
#define cpy(a, b) memcpy(a, b, sizeof a) 
#define rstn(a, v, n) memset(a, v, (n)*sizeof((a)[0])) 
#define cpyn(a, b, n) memcpy(a, b, (n)*sizeof((a)[0])) 
#define pr(x) #x"=" << (x) << " | " 
#define dout  DBG && cerr << __LINE__ << ">>| " 
#define mk(x) DBG && cerr << __LINE__ << "**| "#x << endl 
#define dlist(args...) DBG && (dout << #args", = ", (void)(dbgr, args), cerr << " |" << endl) 
#define ast(b) if(DBG && !(b)) { fprintf(stderr, "%d!!|\n", __LINE__); while(1) getchar(); } 
#define pra(arr, a, b) if(DBG) { \ 
    dout<<#arr"[] | "; \ 
    forlec(i, a, b) cerr<<"["<<i<<"]="<<arr[i]<<" |"<<((i-(a)+1)%13?" ":"\n"); \ 
    if(((b)-(a)+1)%13) cerr<<endl; \ 
  } 
#define rd(type, x) type x; cin >> x 
inline int     rdi() { int d; scanf("%d", &d); return d; } 
inline char    rdc() { scanf(" "); return getchar(); } 
inline string  rds() { rd(string, s); return s; } 
inline double rddb() { double d; scanf("%lf", &d); return d; } 
template<class T> inline bool setmin(T& a, T b) { return a>b? a=b, true: false; } 
template<class T> inline bool setmax(T& a, T b) { return a<b? a=b, true: false; } 
struct debugger { template<typename T> debugger& operator , (const T& x) { cerr << x << ","; return *this; } } dbgr; 
  
typedef long long int64; 
const int N = 512, M = 262144, inf = 0x3f3f3f3f; 
  
int x[N], w[N]; 
  
int64 cost; 
int n, m, s, t; 
int now, d[N], vis[N], instk[N], slack[N]; 
int ne = 1, head[N], cur[N], vex[M], cap[M], cst[M], nxt[M]; 
  
void add_edge(int u, int v, int c, int w) { 
  ++ne; 
  vex[ne] = v; 
  cap[ne] = c; 
  cst[ne] = w; 
  nxt[ne] = head[u]; 
  head[u] = ne; 
} 
void add_2edge(int u, int v, int c, int w) { 
  add_edge(u, v, c, +w); 
  add_edge(v, u, 0, -w); 
} 
  
int dfs(int u, int f) { 
  if(u == t) { cost += (int64)f*d[t]; return f; } 
  vis[u] = instk[u] = now; 
  int sumf = 0; 
  for(int& i = cur[u]; i; i = nxt[i]) if(cap[i]) { 
    int v = vex[i], s = d[u]+cst[i]-d[v], rest = min(f-sumf, cap[i]); 
    if(!rest) continue; 
    setmin(slack[v], s); 
    if(!s && instk[v]!=now) 
      if(int df = dfs(vex[i], rest)) { 
        cap[i  ] -= df; 
        cap[i^1] += df; 
        if((sumf+=df) == f) break; 
      } 
  } 
  instk[u] = false; 
  return sumf; 
} 
bool relabel() { 
  int mins = inf; 
  forle(i, 0, t) if(vis[i] != now) setmin(mins, slack[i]); 
  if(mins == inf) return false; 
  forle(i, 0, t) if(vis[i] != now) d[i] += mins; 
  return true; 
} 
int64 zkwMCMF() { 
  rst(d, 0), cost = 0; 
  do { 
    do cpy(cur, head), rst(slack, 63), ++now; while(dfs(s, inf)); 
  } while(relabel()); 
  return cost; 
} 
  
int main() { 
  m = rdi(), n = rdi(), t = n+m+1; 
  forle(i, 1, n) add_2edge(s, A(i), rdi(), 0); 
  forle(j, 1, m) 
    forle(i, 1, n) 
      if(rdi()) 
        add_2edge(A(i), B(j), inf, 0); 
  forle(j, 1, m) { 
    int k = rdi(); x[k+1] = inf; 
    forle(i, 1, k  ) x[i] = rdi(); 
    forle(i, 1, k+1) w[i] = rdi(); 
    forle(i, 1, k+1) add_2edge(B(j), t, x[i]-x[i-1], w[i]); 
  } 
  cout << zkwMCMF() << endl; 
  return 0; 
}