有上下界的费用流
#include#include #include #include // begin{最小费用最大流}struct edge {int from, to, cap, flow, cost, next;};const int MAXN = 50 + 7;const int inf = 0x3f3f3f3f;edge e[MAXN * MAXN + 7];int head[MAXN * 2 + 7];int e_sz, supS, supT, sum_l;inline void add_edge(int from, int to, int cap, int cost) { if(!cap) return;// printf("%d %d %d %d\n", from, to, cap, cost); e[e_sz].from = from, e[e_sz].to = to, e[e_sz].cap = cap, e[e_sz].cost = cost, e[e_sz].flow = 0, e[e_sz].next = head[from]; head[from] = e_sz++; e[e_sz].from = to, e[e_sz].to = from, e[e_sz].cap = 0, e[e_sz].cost = -cost, e[e_sz].flow = 0, e[e_sz].next = head[to]; head[to] = e_sz++;}inline void add_edge_with_s(int u, int v, int l, int h, int c) { //printf("edge_with_strict %d %d %d %d %d\n", u, v, l, h, c); sum_l += l; add_edge(supS, v, l, c); add_edge(u, supT, l, c); add_edge(u, v, h - l, c);}std::queue q;int dis[MAXN * 2], pre[MAXN * 2]; bool vis[MAXN * 2];bool spfa(int s, int t) { for(int i = 0; i < MAXN * 2; ++i)dis[i] = inf, vis[i] = false, pre[i] = -1; // printf("%d %d\n", s, t); dis[s] = 0, vis[s] = true; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for(int i = head[u], v; i != -1; i = e[i].next) { v = e[i].to; if(e[i].cap > e[i].flow && dis[v] > dis[u] + e[i].cost) { dis[v] = dis[u] + e[i].cost, pre[v] = i; if(!vis[v]) vis[v] = true, q.push(v); } } } return (pre[t] != -1);}//返回的是最大流， cost存的是最小费用int minCostMaxflow(int s, int t, int &cost) { int flow = 0, Min; cost = 0; while(spfa(s, t)) { Min = inf; for(int i = pre[t]; i != -1; i = pre[e[i ^ 1].to]) if(Min > e[i].cap - e[i].flow) Min = e[i].cap - e[i].flow; for(int i = pre[t]; i != -1; i = pre[e[i ^ 1].to]) e[i].flow += Min, e[i ^ 1].flow -= Min, cost += e[i].cost * Min; flow += Min; } return flow;}// end{最小费用最大流}int mat[MAXN][MAXN], Rl[MAXN], Rh[MAXN], Cl[MAXN], Ch[MAXN], cntR[MAXN], cntC[MAXN];int main() { int n,s,t; while(~scanf("%d", &n)) { memset(head, -1, sizeof(head)); e_sz = 0; memset(cntR, 0, sizeof(cntR)); memset(cntC, 0, sizeof(cntC)); s = n * 2 + 1, t = n * 2 + 2; supS = n * 2 + 3, supT = n * 2 + 4, sum_l = 0; for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j)scanf("%d", &mat[i][j]); for(int i = 0; i < n; ++i) scanf("%d%d", Rl + i, Rh + i); for(int i = 0; i < n; ++i) scanf("%d%d", Cl + i, Ch + i); for(int i = 0; i < n; ++i) { for(int j = 0; j < n; j++) cntR[i] += mat[i][j], cntC[i] += mat[j][i]; add_edge_with_s(s, i + 1, cntR[i], cntR[i], 0), add_edge_with_s(s, i + 1 + n, cntC[i], cntC[i], 0); //add_edge(s, i + 1, cntR[i], 0), add_edge(s, i + 1 + n, cntC[i], 0); add_edge_with_s(i + 1, t, Rl[i], Rh[i], 0), add_edge_with_s(i + n + 1, t, Cl[i], Ch[i], 0); } add_edge(t, s, inf, 0); for(int i = 0, x1, x2, y1, y2; i < n * n / 2; ++i) { scanf("%d%d%d%d", &x1, &y1, &x2, &y2); x1--, y1--, x2--, y2--; if(mat[x1][y1] == mat[x2][y2])continue; if(!mat[x1][y1]) std::swap(x1, x2), std::swap(y1, y2); if(x1 == x2) add_edge(y1 + 1 + n, y2 + 1 + n, 1, 1); else if(y1 == y2) add_edge(x1 + 1, x2 + 1, 1, 1); } //printf("input done\n"); int cost, flow = minCostMaxflow(supS, supT, cost);// printf("total flow = %d\n", flow); if(flow != sum_l) puts("-1"); else printf("%d\n", cost); } return 0;}