zkw费用流正版模版 && 预流推进模版
bzoj 2245，速度非常神，代码源自neko13神 预流推进模版
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; }