- //http://www.cnblogs.com/IMGavin/
- #include < iostream > #include < stdio.h > #include < cstdlib > #include < cstring > #include < queue > #include < vector > #include < map > #include < stack > #include < set > #include < bitset > #include < algorithm > using namespace std;
- typedef long long LL;#define gets(A) fgets(A, 1e8, stdin) const int INF = 0x3F3F3F3F,
- N = 1000,
- MOD = 1003,
- M = 1000000;
- const double EPS = 1e-6;
- int ri[N][N],
- up[N][N];
- struct Node {
- int u,
- v,
- cap,
- cost;
- int next;
- }
- edge[M]; //有向图,u到v的容量,费用
- int tot;
- int head[N],
- pre[N],
- path[N],
- dis[N];
- bool inq[N];
- void init() {
- tot = 0;
- memset(head, -1, sizeof(head));
- }
- void add(int u, int v, int cap, int cost) {
- edge[tot].u = u;
- edge[tot].v = v;
- edge[tot].cap = cap;
- edge[tot].cost = cost;
- edge[tot].next = head[u];
- head[u] = tot++;
- edge[tot].u = v;
- edge[tot].v = u;
- edge[tot].cap = 0;
- edge[tot].cost = -cost;
- edge[tot].next = head[v];
- head[v] = tot++;
- }
- bool SPFA(int st, int des) { //计算最小费用
- memset(inq, 0, sizeof(inq));
- memset(dis, 0x3f, sizeof(dis));
- queue < int > q;
- q.push(st);
- dis[st] = 0;
- inq[st] = true;
- while (!q.empty()) {
- int u = q.front();
- q.pop();
- inq[u] = false;
- for (int i = head[u];~i; i = edge[i].next) {
- int v = edge[i].v;
- if (edge[i].cap > 0 && dis[v] > dis[u] + edge[i].cost) {
- dis[v] = dis[u] + edge[i].cost;
- pre[v] = u;
- path[v] = i;
- if (!inq[v]) {
- inq[v] = true;
- q.push(v);
- }
- }
- }
- }
- return dis[des] < INF;
- }
- int EdmondsKarp(int st, int des) { //最小费用最大流
- int mincost = 0,
- flow = 0; //最小费用与流量
- while (SPFA(st, des)) {
- int f = INF;
- for (int i = des; i != st; i = pre[i]) {
- if (f > edge[path[i]].cap) {
- f = edge[path[i]].cap;
- }
- }
- for (int i = des; i != st; i = pre[i]) {
- edge[path[i]].cap -= f;
- edge[path[i] ^ 1].cap += f;
- }
- mincost += f * dis[des];
- flow += f;
- }
- return mincost;
- }
- int main() {
- int a,
- b;
- int p,
- q;
- while (cin >> a >> b) {
- init();
- cin >> p >> q;
- for (int i = 0; i <= p; i++) {
- for (int j = 0; j < q; j++) {
- scanf("%d", &ri[i][j]);
- }
- }
- for (int i = 0; i <= q; i++) {
- for (int j = 0; j < p; j++) {
- scanf("%d", &up[j][i]);
- }
- }
- p++;
- q++;
- int st = p * q,
- des = st + 1;
- for (int i = 0; i < a; i++) {
- int k,
- x,
- y;
- cin >> k >> x >> y;
- add(st, x * q + y, k, 0);
- }
- for (int i = 0; i < b; i++) {
- int k,
- x,
- y;
- cin >> k >> x >> y;
- add(x * q + y, des, k, 0);
- }
- for (int i = 0; i <= p - 1; i++) {
- for (int j = 0; j <= q - 1; j++) {
- if (i < p - 1) {
- add(i * q + j, (i + 1) * q + j, 1, -up[i][j]);
- add(i * q + j, (i + 1) * q + j, INF, 0);
- }
- if (j < q - 1) {
- add(i * q + j, i * q + j + 1, 1, -ri[i][j]);
- add(i * q + j, i * q + j + 1, INF, 0);
- }
- }
- }
- printf("%d\n", -EdmondsKarp(st, des));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-1948872.html