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;   
}