题目大意：

给出n(\(\le 200\))个盒子，第i个盒子长\(x_i\),宽\(y_i\)，一个盒子可以放入长宽都大于等于它的盒子里，并且每个盒子里只能放入一个盒子（可以嵌套），嵌套的盒子的占地面积等于最外层的盒子的占地面积，求最小的占地面积之和。

题目分析：

直接打了贪心，得了50分。用脑子想想就知道第3题怎么可能这么简单，果真。

本题的本质就是能不能给一个盒子找一个长宽都大于等于它的匹配。

匈牙利+贪心：如果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;

}

巴特西

NOIP 模拟 box - 费用流 / 匈牙利

题目大意：

题目分析：

code

最新文章

热门文章