本文共 4073 字，大约阅读时间需要 13 分钟。
题目大意是说有一个B矩阵，现在A是一个空矩阵（每个元素都为0）,每次操作可以将A矩阵相邻的两个元素同时+1，但是有个要求就是A矩阵的每个元素都不可以超过K，求
这个的最小值
解题思路是这样的，新建起点与奇点（i != j）连K条边，第i条边的权值为(i - B)^2 - (i - 1 - B)^2 = 2 * i - 1 - 2 * B（这样可以保证如果此边的流量为a, 花费始终是(a-b)^2）;另外新建终点与偶点相连，代价与上诉一致；
然后跑一遍最小费用流，知道cost>=0时为止。祥见代码：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 using namespace std; 15 #define INF 0x3f3f3f3f 16 #define inf (-((LL)1<<40)) 17 #define lson k<<1, L, mid 18 #define rson k<<1|1, mid+1, R 19 #define mem0(a) memset(a,0,sizeof(a)) 20 #define mem1(a) memset(a,-1,sizeof(a)) 21 #define mem(a, b) memset(a, b, sizeof(a)) 22 #define FIN freopen("in.txt", "r", stdin) 23 #define FOUT freopen("out.txt", "w", stdout) 24 #define rep(i, a, b) for(int i = a; i <= b; i ++) 25 26 template T CMP_MIN(T a, T b) { return a < b; } 27 template T CMP_MAX(T a, T b) { return a > b; } 28 template T MAX(T a, T b) { return a > b ? a : b; } 29 template T MIN(T a, T b) { return a < b ? a : b; } 30 template T GCD(T a, T b) { return b ? GCD(b, a%b) : a; } 31 template T LCM(T a, T b) { return a / GCD(a,b) * b; } 32 33 //typedef __int64 LL; 34 typedef long long LL; 35 const int MAXN = 10010; 36 const int MAXM = 20010; 37 const double eps = 1e-4; 38 39 40 const int dx[4] = { 0, 1, 0, -1}; 41 const int dy[4] = { 1, 0, -1, 0}; 42 int T, N, M, K, B, ans = 0; 43 44 /*******************************************************************/ 45 struct Edge { 46 int to, cap, flow, cost, next; 47 Edge(){} 48 Edge(int _n, int _v, int _c, int _f, int _cost){ 49 next = _n; to = _v; cap = _c; 50 flow = _f; cost = _cost; 51 } 52 }; 53 54 struct MCMF 55 { 56 int n, m, src, des; 57 int head[MAXN], tot; 58 Edge edges[MAXM]; 59 int inq[MAXN]; 60 int d[MAXN]; 61 int p[MAXN]; 62 int a[MAXN]; 63 64 void init(int n) { 65 this->tot = 0; 66 this->n = n; 67 mem1(head); 68 } 69 70 void add_edge(int from, int to, int cap, int cost) { 71 edges[tot] = Edge(head[from], to, cap, 0, cost); 72 head[from] = tot ++; 73 edges[tot] = Edge(head[to], from, 0, 0, -cost); 74 head[to] = tot ++; 75 } 76 77 bool bellman_ford(int s, int t, int& flow) { 78 for(int i = 0; i < n; i ++) { 79 d[i] = INF; 80 inq[i] = 0; 81 } 82 d[s] = 0; inq[s] = 1; 83 p[s] = 0; a[s] = INF; 84 85 queue Q; 86 Q.push(s); 87 while(!Q.empty()) { 88 int u = Q.front(); Q.pop(); 89 inq[u] = false; 90 for(int i = head[u]; i != -1; i = edges[i].next) { 91 int v = edges[i].to; 92 if(edges[i].cap > edges[i].flow && d[v] > d[u] + edges[i].cost) { 93 d[v] = d[u] + edges[i].cost; 94 p[v] = i; 95 a[v] = min(a[u], edges[i].cap - edges[i].flow); 96 if(!inq[v]) { 97 Q.push(v); 98 inq[v] = 1; 99 }100 }101 }102 }103 if(d[t] >= 0) return false;104 105 flow += a[t];106 ans += d[t] * a[t];107 108 int u = t;109 while(u != s) {110 edges[p[u]].flow += a[t];111 edges[p[u]^1].flow -= a[t];112 u = edges[p[u]^1].to;113 }114 return true;115 }116 117 int min_cost(int s, int t) {118 int flow = 0;119 while(bellman_ford(s, t, flow));120 return ans;121 }122 123 };124 /***************************************************************/125 126 int idx(int i, int j) {127 return (i - 1) * M + j;128 }129 130 int ok(int i, int j) {131 return (i >= 1 && i <= N && j >= 1 && j <= M);132 }133 134 135 MCMF mcmf;136 137 int main()138 {139 //FIN;140 cin >> T;141 rep (t, 1, T) {142 scanf("%d %d %d", &N, &M, &K);143 mcmf.init(N * M + 2);144 mcmf.src = 0; mcmf.des = N * M + 1; ans = 0;145 rep (i, 1, N) rep (j, 1, M) {146 scanf("%d", &B);147 ans += B * B;148 if(i % 2 == j % 2) rep (k, 1, K) {149 mcmf.add_edge(mcmf.src, idx(i, j), 1, 2 * k - 1 - 2 * B);150 rep (k, 0, 3) if(ok(i + dx[k], j + dy[k])) {151 mcmf.add_edge(idx(i, j), idx(i + dx[k], j + dy[k]), INF, 0);152 }153 }154 else rep (k, 1, K) {155 mcmf.add_edge(idx(i, j), mcmf.des, 1, 2 * k - 1 - 2 * B);156 }157 }158 printf("Case %d: %d\n", t, mcmf.min_cost(mcmf.src, mcmf.des));159 }160 return 0;161 }
转载于:https://www.cnblogs.com/gj-Acit/p/4374951.html
