#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdio>
#include <vector> using namespace std; const int N = + ;
const int oo = 0x3f3f3f3f; struct Edge {
int from, to, cap, flow;
}; struct Dinic {
int n, m, s, t;
int dis[N], cur[N], que[N << ];
bool vis[N];
vector <Edge> edges;
vector <int> G[N]; void add(int from, int to, int cap) {
edges.push_back((Edge) {from, to, cap, });
edges.push_back((Edge) {to, from, , });
m = edges.size();
G[from].push_back(m - );
G[to].push_back(m - );
} bool bfs() {
int head = , tail = ; memset(vis, false, sizeof vis);
dis[s] = ; vis[s] = true; que[head] = s;
while(head <= tail) {
int x = que[head]; for(int i = ; i < (signed) G[x].size(); ++ i) {
Edge &e = edges[G[x][i]]; if(!vis[e.to] && e.cap > e.flow) {
vis[e.to] = true;
dis[e.to] = dis[x] + ;
que[++ tail] = e.to;
}
}
++ head;
}
return vis[t];
} int dfs(int x, int a) {
if(x == t || a == ) return a; int flw = , f; for(int &i = cur[x]; i < (signed) G[x].size(); ++ i) {
Edge &e = edges[G[x][i]]; if(dis[e.to] == dis[x] + && (f = dfs(e.to, min(a, e.cap - e.flow))) > ) {
e.flow += f; edges[G[x][i] ^ ].flow -= f; flw += f; a -= f;
if(a == ) break;
}
}
return flw;
} int MaxFlow(int s, int t) {
this->s = s; this->t = t; int flw = ; while(bfs()) {
memset(cur, , sizeof cur);
flw += dfs(s, oo);
}
return flw;
}
}net; int n, M[N]; int main() {
#ifndef ONLINE_JUDGE
freopen("maxflowb.in", "r", stdin);
freopen("maxflowb.out", "w", stdout);
#endif int Up, Down; scanf("%d", &n); net.n = n + ;
for(int i = ; i <= n; ++ i) {
for(int j = ; j <= n; ++ j) {
scanf("%d%d", &Down, &Up);
M[i] -= Down; M[j] += Down;
net.add(i, j, Up - Down);
}
}
net.add(n, , oo);
for(int i = ; i <= n; ++ i) {
if(M[i] > ) {
net.add(, i, M[i]);
}
else if(M[i] < ){
net.add(i, n + , -M[i]);
}
}
net.MaxFlow(, n + );
printf("%d\n", net.MaxFlow(, n)); #ifndef ONLINE_JUDGE
fclose(stdin); fclose(stdout);
#endif
return ;
}
Cogs 12
连边方式见图。