題目大意：

給出n(\(\le 200\))個盒子，第i個盒子長\(x_i\),寬\(y_i\)，一個盒子可以放入長寬都大于等于它的盒子里，并且每個盒子里只能放入一個盒子（可以嵌套），嵌套的盒子的占地面積等于最外層的盒子的占地面積，求最小的占地面積之和。

題目分析：

直接打了貪心，得了50分。用腦子想想就知道第3題怎么可能這么簡單，果真。
本題的本質(zhì)就是能不能給一個盒子找一個長寬都大于等于它的匹配。

• 匈牙利+貪心：如果a可以包含b，則連一條邊a<-b，然后按照面積從大到小跑匈牙利，如果能夠找到一個匹配，就把這個盒子的面積減掉。
• 費用流： 將一個盒子拆成兩個點1~n, n+1~2n, 如果a可以包含b，就連一條a->b+n，流量為1（只能用1個），費用為\(S_b\)的邊，最后從s向1~n連流量為1，費用為0的邊，從n+1~2n向t連流量為1，費用為0的邊，跑最大費用最大流，將費用從總面積中減去。(費用流要去重)

code

匈牙利

#include<bits/stdc++.h> using namespace std;namespace IO{inline int read(){int i = 0, f = 1; char ch = getchar();for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());if(ch == '-') f = -1, ch = getchar();for(; ch >= '0' && ch <= '9'; ch = getchar()) i = (i << 3) + (i << 1) + (ch - '0');return i * f;}inline void wr(int x){if(x < 0) putchar('-'), x = -x;if(x > 9) wr(x / 10);putchar(x % 10 + '0');} }using namespace IO;const int N = 1000; int n; struct node{int x, y;inline bool operator < (const node &b) const{return x*y < b.x*b.y;} }box[N]; bool vst[N << 2]; int mateR[N << 2], ecnt, adj[N << 2], nxt[N << 2], go[N << 2], ans, to[N][N];inline bool hungry(int u){for(int i = n; i > u; i--){if(!to[u][i]) continue;if(vst[i]) continue;vst[i] = true;if(!mateR[i] || hungry(mateR[i])){mateR[i] = u;return true;}}return false; }inline void addEdge(int u, int v){nxt[++ecnt] = adj[u], adj[u] = ecnt, go[ecnt] = v; }int main(){n = read();for(int i = 1; i <= n; i++){int x = read(), y = read();box[i] = (node){x, y};}sort(box + 1, box + n + 1);for(int i = 1; i <= n; i++){ans += box[i].x * box[i].y;for(int j = i + 1; j <= n; j++){if(box[i].x <= box[j].x && box[i].y <= box[j].y)to[i][j] = 1;}}for(int i = n - 1; i >= 1; i--){if(hungry(i)) ans -= box[i].x * box[i].y;memset(vst, 0, sizeof vst);}wr(ans);return 0; }

費用流

#include<bits/stdc++.h> using namespace std;namespace IO{inline int read(){int i = 0, f = 1; char ch = getchar();for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());if(ch == '-') f = -1, ch = getchar();for(; ch >= '0' && ch <= '9'; ch = getchar()) i = (i << 3) + (i << 1) + (ch - '0');return i * f;}inline void wr(int x){if(x < 0) putchar('-'), x = -x;if(x > 9) wr(x / 10);putchar(x % 10 + '0');} }using namespace IO;const int N = 205, OO = 0x3f3f3f3f; int n, ecnt = 1, adj[N << 2], nxt[100050], go[100050], cap[100050], len[100050]; int src, des, dis[N << 2], cur[N << 2], sum; struct node{int x, y;inline bool operator < (const node &b) const{return x < b.x || (x == b.x && y < b.y);} }box[N], unik[N];inline void addEdge(int u, int v, int c, int cost){nxt[++ecnt] = adj[u], adj[u] = ecnt, go[ecnt] = v, cap[ecnt] = c, len[ecnt] = cost;nxt[++ecnt] = adj[v], adj[v] = ecnt, go[ecnt] = u, cap[ecnt] = 0, len[ecnt] = -cost; }int vt = 0; inline bool SPFA(){static queue<int> que;static int vst[N << 2];memset(vst, 0, sizeof vst);while(!que.empty()) que.pop();que.push(src);for(int i = src; i <= des; i++) cur[i] = adj[i], dis[i] = -OO;dis[src] = 0;while(!que.empty()){int u = que.front(); que.pop(); vst[u] = 0;for(int e = adj[u]; e; e = nxt[e]){int v = go[e];if(dis[v] < dis[u] + len[e] && cap[e]){dis[v] = dis[u] + len[e];if(!vst[v]) vst[v] = 1, que.push(v);}}}return dis[des] != -OO; }bool walk[N << 2]; inline int dinic(int u, int flow, int &ans){if(u == des){ans += flow * dis[u];return flow;}int delta, ret = 0;walk[u]=1;for(int &e = cur[u]; e; e = nxt[e]){int v = go[e];if(!walk[v] && dis[v] == dis[u] + len[e] && cap[e]){delta = dinic(v, min(cap[e], flow - ret), ans);if(delta){ret += delta, cap[e] -= delta, cap[e ^ 1] += delta;if(flow == ret) break;}}}if(flow != ret) dis[u] = -OO;return ret; }int lenn; inline void uni(){lenn = 0;sort(box+1,box+n+1);for(int i = 1; i <= n; i++){if(box[i].x != box[i - 1].x || box[i].y != box[i - 1].y)unik[++lenn].x = box[i].x, unik[lenn].y = box[i].y;} } int main(){n = read(); src = 0, des = 2 * n + 1;for(int i = 1; i <= n; i++) box[i].x = read(), box[i].y = read();uni();for(int i = 1; i <= lenn; i++){sum += unik[i].x * unik[i].y;for(int j = 1; j <= lenn; j++){if(i == j) continue;if(unik[j].x >= unik[i].x && unik[j].y >= unik[i].y) addEdge(i, j + n, 1, unik[i].x*unik[i].y);}}for(int i = 1; i <= n; i++) addEdge(src, i, 1, 0), addEdge(i + n, des, 1, 0);while(SPFA()){int ret = 0;memset(walk, 0, sizeof walk);dinic(src, OO, ret);sum -= ret;}wr(sum), putchar('\n');return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/CzYoL/p/7694086.html

總結(jié)

以上是生活随笔為你收集整理的NOIP 模拟 box - 费用流 / 匈牙利的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。