做网站月入7000,建立企业网站方案,罗岗网站建设价格,网站没快照要分成两坨对吧。。 所以显然最小割 但是不兹辞啊。。 最小割是最小的啊 求最大费用怎么玩啊 那咱们就把所有费用都加起来#xff0c;减掉一个最小的呗 但是两个属于不同集合的点贡献的价值是负的啊 网络流怎么跑负的啊 那咱就交换一下呗 原图是二分图啊#xff0c;把另一部分…要分成两坨对吧。。 所以显然最小割 但是不兹辞啊。。 最小割是最小的啊 求最大费用怎么玩啊 那咱们就把所有费用都加起来减掉一个最小的呗 但是两个属于不同集合的点贡献的价值是负的啊 网络流怎么跑负的啊 那咱就交换一下呗 原图是二分图啊把另一部分与S和T连边的流量换一下就好啦。 注意哦 n和m可能为1 所以累加C的时候写成ans C[i][j] * (4 - (i 1 || i n) - (j 1 || j m));就错啦。 要么在加边的时候累加要么写成ans C[i][j] * ((i ! 1) (i ! n) (j ! 1) (j ! m)); 1 #includecstdio2 #includecstring3 #includecstdlib4 #includealgorithm5 #includeiostream6 #define rep(i, a, b) for(int i (a), _end (b); i _end; i)7 8 using namespace std;9 10 void setIO(const string s) {11 freopen((s .in).c_str(), r, stdin);12 freopen((s .out).c_str(), w, stdout);13 }14 templatetypename Q Q read(Q x) {15 static char c, f;16 for(f 0; c getchar(), !isdigit(c); ) if(c -) f 1;17 for(x 0; isdigit(c); c getchar()) x x * 10 c - 0;18 if(f) x -x;19 return x;20 }21 templatetypename Q Q read() {22 static Q x; read(x); return x;23 }24 25 // ISAP26 const int N 100 * 100 10, M 100 * 100 * 4 10, INF ~0u 1;27 28 struct Edge {29 int to, adv;30 Edge *next;31 Edge(int to 0, int adv 0, Edge *next 0) : to(to), adv(adv), next(next) {}32 }pool[M * 2], *pis pool, *fir[N], *pre[N];33 34 void AddEdge(int u, int v, int w, int b 0) {35 fir[u] new(pis) Edge(v, w, fir[u]);36 fir[v] new(pis) Edge(u, w * b, fir[v]);37 }38 39 Edge *inv(Edge *p) {40 return pool ((p - pool) ^ 1);41 }42 43 int d[N], q[N], ql, qr;44 45 namespace ISAP {46 int n, s, t;47 int num[N];48 Edge *cur[N];49 50 void insert(int u, int dis) {51 if(d[u] n) {52 d[u] dis;53 q[qr] u;54 }55 }56 57 void BFS() {58 for(int u 1; u n; u) {59 d[u] n;60 }61 ql qr 0;62 insert(t, 0);63 while(ql ^ qr) {64 int u q[ql];65 for(Edge *p fir[u]; p; p p-next) if(inv(p)-adv){66 insert(p-to, d[u] 1);67 }68 }69 }70 71 int Augment() {72 int a INF;73 for(int u t; u ! s; u inv(pre[u])-to) {74 a min(a, pre[u]-adv);75 }76 for(int u t; u ! s; u inv(pre[u])-to) {77 pre[u]-adv - a;78 inv(pre[u])-adv a;79 }80 return a;81 }82 83 int Maxflow() {84 memset(num, 0, sizeof num);85 BFS();86 for(int u 1; u n; u) {87 cur[u] fir[u];88 num[d[u]];89 }90 for(int i 1; i d[s]; i) {91 if(!num[i]) return 0;92 }93 int flow 0;94 for(int u s; d[s] n; ) {95 if(u t) {96 flow Augment();97 u s;98 }99 int ok 0;
100 for(Edge *p cur[u]; p; p p-next) if(p-adv) {
101 int v p-to;
102 if(d[v] 1 d[u]) {
103 pre[u v] p;
104 ok 1;
105 break;
106 }
107 }
108 if(!ok) {
109 int dis d[u];
110 if(!--num[dis]) break;
111 dis n;
112 for(Edge *p (cur[u] fir[u]); p; p p-next) if(p-adv) {
113 dis min(dis, d[p-to] 1);
114 }
115 num[dis];
116 if(u ! s) u inv(pre[u])-to;
117 }
118 }
119 return flow;
120 }
121
122 int main(int _n, int _s, int _t) {
123 n _n, s _s, t _t;
124 return Maxflow();
125 }
126 }
127
128 int n, m;
129
130 int encode(int x, int y) {
131 return (x - 1) * m y;
132 }
133
134 const int maxn 100 10;
135
136 int A[maxn][maxn], B[maxn][maxn], C[maxn][maxn];
137
138 int main() {
139 #ifdef DEBUG
140 freopen(in.txt, r, stdin);
141 freopen(out.txt, w, stdout);
142 #endif
143
144 read(n), read(m);
145 int ans 0;
146 rep(i, 1, n) rep(j, 1, m) ans read(A[i][j]);
147 rep(i, 1, n) rep(j, 1, m) ans read(B[i][j]);
148 rep(i, 1, n) rep(j, 1, m) read(C[i][j]);
149 int s n * m 1, t s 1;
150 rep(i, 1, n) rep(j, 1, m) {
151 int u encode(i, j);
152 if((i ^ j) 1) swap(A[i][j], B[i][j]);
153 AddEdge(s, u, A[i][j]);
154 AddEdge(u, t, B[i][j]);
155 if(i n) AddEdge(u, encode(i 1, j), C[i][j] C[i1][j], 1), ans C[i][j] C[i1][j];
156 if(j m) AddEdge(u, encode(i, j 1), C[i][j] C[i][j1], 1), ans C[i][j] C[i][j1];
157 }
158
159 printf(%d\n, ans - ISAP::main(t, s, t));
160
161 return 0;
162 } View Code 转载于:https://www.cnblogs.com/showson/p/5043565.html
