《算法竞赛进阶指南》 0x68 ~ 0x67 代码 + 杂谈

二分图最大匹配

之前 一直没有学匈牙利 只写DINIC 匈牙利也挺简单的 关键是好写多了orz

关押罪犯

https://blog.csdn.net/qq_40831340/article/details/88821278

棋盘覆盖

我依稀的记得 第一次见到是DP来着

#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
const int cx[] = {-1, 0, 1, 0};
const int cy[] = {0, 1, 0, -1};

int n, k;
bool mp[maxn][maxn], vis[maxn * maxn];

int head[maxn * maxn], match[maxn * maxn], cnt;
int nxt[maxn * maxn << 2], to[maxn * maxn << 2];


void ade(int a, int b) {
    to[++cnt] = b;
    nxt[cnt] = head[a], head[a] = cnt;
}

int ids(int i, int j) {
    return (i) * n + j;
}

bool chk(int i, int j) {
    if(i < 1 || i > n || j < 1 || j > n) return 0;
    if(mp[i][j]) return 0;
    return 1;
}

bool dfs(int x) {
    for(int i = head[x], y; i; i = nxt[i]) {
        if(!vis[y = to[i]]) {
            vis[y] = 1;
            if(!match[y] || dfs(match[y])) {
                match[y] = x; return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> k;
    for(int i = 1, a, b; i <= k; i ++) {
        cin >> a >> b;
        mp[a][b] = 1;
    }
    
    for(int i = 1; i <= n; i ++) {
        for(int j = (i % 2 ? 1 : 2); j <= n; j += 2) {
            for(int z = 0; z < 4; z ++) {
                if(chk(i + cx[z], j + cy[z]))
                    ade(ids(i, j), ids(i + cx[z], j + cy[z])), ade(ids(i + cx[z], j + cy[z]), ids(i, j));
            }
        }
    }
    
    int ans = 0;
    for(int i = 1; i <= n; i ++) {
        for(int j = (i % 2 ? 1 : 2); j <= n; j += 2) {
            if(mp[i][j]) continue;
            memset(vis, 0, sizeof vis);
            if(dfs(ids(i, j))) ans ++;
        }
    }
    cout << ans << endl;
    return 0;
}
车的放置

把行和列当 左右匹配点

#include <bits/stdc++.h>
using namespace std;
const int maxn = 205;
const int cx[] = {-1, 0, 1, 0};
const int cy[] = {0, 1, 0, -1};

int n, m, k;
bool mp[maxn][maxn], vis[maxn * maxn];

int head[maxn * maxn], match[maxn * maxn], cnt;
int nxt[maxn * maxn << 2], to[maxn * maxn << 2];


void ade(int a, int b) {
    to[++cnt] = b;
    nxt[cnt] = head[a], head[a] = cnt;
}

bool chk(int i, int j) {
    if(i < 1 || i > n || j < 1 || j > n) return 0;
    if(mp[i][j]) return 0;
    return 1;
}

bool dfs(int x) {
    for(int i = head[x], y; i; i = nxt[i]) {
        if(!vis[y = to[i]]) {
            vis[y] = 1;
            if(!match[y] || dfs(match[y])) {
                match[y] = x; return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m >> k;
    for(int i = 1, a, b; i <= k; i ++) {
        cin >> a >> b;
        mp[a][b] = 1;
    }
    
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) {
            if(!mp[i][j]) ade(i, j + n),ade(j + n, i);
        }
    }
    
    int ans = 0;
    for(int i = 1; i <= n; i ++) {
            memset(vis, 0, sizeof vis);
            if(dfs(i)) ans ++;
    }
    cout << ans << endl;
    return 0;
}
导弹防御塔

https://blog.csdn.net/qq_40831340/article/details/97746759

二分图 带权匹配

一般费用流最大价值 边取反处理
补上 蚂蚁那道题 既然线不相交 那样 他们之间距离就会保持最小

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 2e4 + 10;

int n, m, s, t;
int head[maxn], cnt;
int nxt[maxn << 1], to[maxn << 1], cap[maxn << 1];
double cost[maxn << 1];
int ans[maxn];

void ade(int a, int b, int w, double c) {
    to[cnt] = b, cost[cnt] = c, cap[cnt] = w;
    nxt[cnt] = head[a], head[a] = cnt++;
}

bool vis[maxn];
double dis[maxn];
int flow[maxn], pre[maxn], last[maxn];

bool spfa() {
    queue<int> que;
    memset(flow, 0x3f, sizeof(flow));
    memset(vis, 0, sizeof(vis));
    fill(dis, dis + 2 * n + 3, 1e12);
    que.push(s);
    vis[s] = 1;
    dis[s] = 0;
    pre[t] = -1;
    flow[s] = INF;
    while(!que.empty()) {
        int now = que.front(); que.pop();
        vis[now] = 0;
        for(int i = head[now]; ~i ; i = nxt[i]) {
            if(cap[i] && dis[to[i]] > dis[now] + cost[i]) {
                dis[to[i]] = dis[now] + cost[i];
                pre[to[i]] = now;
                last[to[i]] = i;
                flow[to[i]] = min(flow[now], cap[i]);
                if(!vis[to[i]]) {
                    vis[to[i]] = 1;
                    que.push(to[i]);
                }
            }
        }
    }
    return pre[t] != -1;
}

double mincost;
int maxflow;

void MCMF() {
    while(spfa()) {
        int now = t;
        maxflow += flow[t];
        mincost += 1.0 * flow[t] * dis[t];
        while(now != s) {
            cap[last[now]] -= flow[t];
            cap[last[now] ^ 1] += flow[t];
            now = pre[now];
        }
    }
}

struct point {
    int x, y;
} a[105], b[105];

double redis(int i, int j) {
    return sqrt((a[i].x - b[j].x) * (a[i].x - b[j].x) + (a[i].y - b[j].y) * (a[i].y - b[j].y));
}

signed main() {
    fastio;
    memset(head, -1, sizeof(head));
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i].x >> a[i].y;
    for(int i = 1; i <= n; i ++) cin >> b[i].x >> b[i].y;
    s = 0, t = 2 * n + 1;
    
    for(int i = 1; i <= n; i++) {
        ade(s, i, 1, 0), ade(i, s, 0, 0);
        ade(i + n, t, 1, 0), ade(t, i + n, 0, 0);
    }
    
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= n; j ++) {
            double len = redis(i, j);
            ade(i, j + n, 1, len), ade(j + n, i, 0, -len);
        }
    }
    MCMF();
    
    for(int u = 1; u <= n; u++) {
        for(int i = head[u]; ~i; i = nxt[i]) {
            if(cap[i] == 0) ans[u] = to[i] - n;
        }
    }
    
    for(int i = 1; i <= n; i++) {
        cout << ans[i] << endl;
    }
    // cout << maxflow << " " << mincost << endl;
    return 0;
}

二分图覆盖

最小点覆盖 = 最大匹配
相对于二分图匹配完的边 每个边上二者至少选一个 覆盖所有边

任务机器
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;

int n, m, k;
int head[maxn << 1], match[maxn << 1], cnt;
int nxt[maxn << 1], to[maxn << 1];
bool vis[maxn << 1];

void ade(int a, int b) {
    to[++cnt] = b;
    nxt[cnt] = head[a], head[a] = cnt;
}

bool dfs(int x) {
    for(int i = head[x], y; i; i = nxt[i]) {
        if(!vis[y = to[i]]){
            vis[y] = 1;
            if(!match[y] || dfs(match[y])){
                match[y] = x; return true;
            }
        }
    } 
    return false;
}

int main() {
    while(cin >> n && n) {
        cin >> m >> k;
        memset(head, 0, sizeof head);
        memset(match, 0, sizeof match);
        cnt = 0;
        for(int i = 1, a, b, c; i <= k; i ++) {
            cin >> c >> a >> b;
            if(a == 0 || b == 0) continue;
            ade(a, b + n + 1), ade(b + n + 1, a);
        }
        int ans = 0;
        for(int i = 1; i <= n; i ++){
            memset(vis, 0, sizeof vis);
            if(dfs(i)) ans ++ ;
        }
        cout << ans << endl;
    }
    
    return 0;
}
泥泞的区域

与网络流一样 还是建图是最难写的地方。。。。。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;

int n, m;
char mp[maxn][maxn];
int h[maxn][maxn], l[maxn][maxn];
int head[maxn], match[maxn], cnt;
int nxt[maxn << 1], to[maxn << 1];
bool vis[maxn];

void ade(int a, int b) {
    to[++ cnt] = b;
    nxt[cnt] = head[a], head[a] = cnt;
}

bool dfs(int x) {
    for(int i = head[x], y; i; i = nxt[i]) {
        if(!vis[y = to[i]]) {
            vis[y] = 1;
            if(!match[y] || dfs(match[y])) {
                match[y] = x; return true;
            }
        }
    }
    return false;
}

int main() {
    scanf ("%d %d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%s", mp[i] + 1);
    int tot = 0;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) {
            if(mp[i][j] == '*') {
                if(mp[i][j - 1] == '*') h[i][j] = tot;
                else h[i][j] = ++tot;
            }
        }
    }
    
    for(int i = 1; i <= m; i ++) {
        for(int j = 1; j <= n; j ++) {
            if(mp[j][i] == '*') {
                if(mp[j - 1][i] == '*') l[j][i] = tot;
                else l[j][i] = ++tot;
            }
        }
    }
    
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) {
            if(l[i][j] && h[i][j]) {
                ade(l[i][j], h[i][j]), ade(h[i][j], l[i][j]);
            }
        }
    }
    // for(int i = 1; i <= n; i ++) {
    // for(int j = 1; j <=m;j ++) {
    // cout << h[i][j] << " ";
    // }cout << endl;
    // }
    
    // for(int i = 1; i <= n; i ++) {
    // for(int j = 1; j <=m;j ++) {
    // cout << l[i][j] << " ";
    // }cout << endl;
    // }
    
    int ans = 0;
    for(int i = 1; i <= tot; i ++) {
        memset(vis, 0, sizeof vis);
        if(dfs(i)) ans ++;
    }
    cout << ans / 2<< endl;
    return 0;
}

二分图最大独立集

任何点之间 都没有边链接

骑士放置
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;

int n, m, k;
int mp[105][105];
int head[maxn], match[maxn], cnt;
int nxt[maxn << 1], to[maxn << 1];
bool vis[maxn];

const int cx[10]={-1, -2, -1, -2, 1, 2, 1, 2};
const int cy[10]={-2, -1, 2, 1, -2, -1, 2, 1};

int ids(int i, int j) {
    return (i - 1) * m + j;
}

bool chk(int x, int y) {
    if(x < 1 || y < 1 || x > n || y > m || mp[x][y]) return 1;
    else return 0;
}

void ade(int a, int b) {
    to[++ cnt] = b;
    nxt[cnt] = head[a], head[a] = cnt;
}

bool dfs(int x) {
    for(int i = head[x], y; i; i = nxt[i]) {
        if(!vis[y = to[i]]) {
            vis[y] = 1;
            if(!match[y] || dfs(match[y])) {
                match[y] = x; return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m >> k;
    for(int i = 1, a, b; i <= k; i ++) {
        cin >> a >> b;
        mp[a][b] = 1;
    }
    
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) {
            if(mp[i][j]) continue;
            for(int z = 0; z < 8; z ++) {
                int nx = i + cx[z], ny = j + cy[z];
                if(chk(nx, ny)) continue;
                ade(ids(i, j), ids(nx, ny));
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++ ) {
            if(mp[i][j]) continue;
            memset(vis, 0, sizeof vis);
            if(dfs(ids(i, j))) ans ++;
        }
    }
    cout << n * m - ans/2 - k << endl;
    return 0;
}
ANT

带权二分图匹配 费用流写法

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 2e4 + 10;

int n, m, s, t;
int head[maxn], cnt;
int nxt[maxn << 1], to[maxn << 1], cap[maxn << 1];
double cost[maxn << 1];
int ans[maxn];

void ade(int a, int b, int w, double c) {
    to[cnt] = b, cost[cnt] = c, cap[cnt] = w;
    nxt[cnt] = head[a], head[a] = cnt++;
}

bool vis[maxn];
double dis[maxn];
int flow[maxn], pre[maxn], last[maxn];

bool spfa() {
    queue<int> que;
    memset(flow, 0x3f, sizeof(flow));
    memset(vis, 0, sizeof(vis));
    fill(dis, dis + 2 * n + 3, 1e12);
    que.push(s);
    vis[s] = 1;
    dis[s] = 0;
    pre[t] = -1;
    flow[s] = INF;
    while(!que.empty()) {
        int now = que.front(); que.pop();
        vis[now] = 0;
        for(int i = head[now]; ~i ; i = nxt[i]) {
            if(cap[i] && dis[to[i]] > dis[now] + cost[i]) {
                dis[to[i]] = dis[now] + cost[i];
                pre[to[i]] = now;
                last[to[i]] = i;
                flow[to[i]] = min(flow[now], cap[i]);
                if(!vis[to[i]]) {
                    vis[to[i]] = 1;
                    que.push(to[i]);
                }
            }
        }
    }
    return pre[t] != -1;
}

double mincost;
int maxflow;

void MCMF() {
    while(spfa()) {
        int now = t;
        maxflow += flow[t];
        mincost += 1.0 * flow[t] * dis[t];
        while(now != s) {
            cap[last[now]] -= flow[t];
            cap[last[now] ^ 1] += flow[t];
            now = pre[now];
        }
    }
}

struct point {
    int x, y;
} a[105], b[105];

double redis(int i, int j) {
    return sqrt((a[i].x - b[j].x) * (a[i].x - b[j].x) + (a[i].y - b[j].y) * (a[i].y - b[j].y));
}

signed main() {
    fastio;
    memset(head, -1, sizeof(head));
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i].x >> a[i].y;
    for(int i = 1; i <= n; i ++) cin >> b[i].x >> b[i].y;
    s = 0, t = 2 * n + 1;
    
    for(int i = 1; i <= n; i++) {
        ade(s, i, 1, 0), ade(i, s, 0, 0);
        ade(i + n, t, 1, 0), ade(t, i + n, 0, 0);
    }
    
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= n; j ++) {
            double len = redis(i, j);
          // cout << len << endl;
            ade(i, j + n, 1, len), ade(j + n, i, 0, -len);
        }
    }
    MCMF();
    
    for(int u = 1; u <= n; u++) {
        for(int i = head[u]; ~i; i = nxt[i]) {
            if(cap[i] == 0) ans[u] = to[i] - n;
        }
    }
    
    for(int i = 1; i <= n; i++) {
        cout << ans[i] << endl;
    }    
    // cout << maxflow << " " << mincost << endl;
    return 0;
}

有向无环图最小路径点覆盖 待续

全部评论

相关推荐

11-26 17:09
华南理工大学 后端
offer选择 华为 蚂蚁 pdd
蚂蚁 基架java (n+6)*16 签字费若干
点赞 评论 收藏
分享
11-25 10:19
门头沟学院 商业技术工程师
阿里云VS腾讯VS华为，决赛圈
bg：24届华科本，计算机专业。又到了一年一度offer&nbsp;pk的时刻了，想到了我去年也是同时拿到了阿里云、腾讯、华为的管培生offer，最终选择了阿里云，给大家分享一下我的决策过程，希望能够帮到你们。这几个offer本质上都是偏销售类型的，因为我当时很明确自己想做这种技术复合人才，一方面是我的性格比较适合，另一方面我觉得发展空间更大，所以我投递的基本都是这种岗位，我称之为懂技术的销售！幸运的是，我拿到了行业中比较顶级的3个销售管培offer，分别是：阿里云，商业技术工程师，今年叫阿里云管培生（商业技术方向）腾讯，销售管培，广告方向华为，华为云客户经理机智的我采用了逐一淘汰机制...
offer王中王：真好啊，还得是9本，进可攻退可守
投递腾讯等公司10个岗位 >
点赞 评论 收藏
分享
10-08 14:04
门头沟学院 测试开发
点赞 评论 收藏
分享
10-11 19:44
已编辑
门头沟学院 Java
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
11-28 23:13
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
236137次浏览 2038人参与
# ai智能作图 #
26598次浏览 315人参与
# 阿里云管培生offer #
61467次浏览 1756人参与
# 25届秋招总结 #
406145次浏览 4071人参与
# 25届机械人为了秋招做了哪些准备？ #
25984次浏览 363人参与
# 地方国企笔面经互助 #
6810次浏览 16人参与
# 北方华创开奖 #
66711次浏览 551人参与
# 机械求职避坑tips #
23293次浏览 249人参与
# 实习，投递多份简历没人回复怎么办 #
2438958次浏览 34731人参与
# 软件开发投递记录 #
1480570次浏览 23940人参与
# 虾皮求职进展汇总 #
88510次浏览 714人参与
# 我的实习求职记录 #
6129097次浏览 84002人参与
# 我在牛爱网找对象 #
74699次浏览 554人参与
# 机械人怎么评价今年的华为 #
157652次浏览 1350人参与
# 你觉得通信/硬件有必要实习吗？ #
54708次浏览 695人参与
# 歌尔求职进展汇总 #
42862次浏览 294人参与
# 如果可以，你希望哪个公司来捞你 #
33236次浏览 193人参与
# 如果再来一次，你还会选择这个工作吗？ #
114236次浏览 1131人参与
# 如何写一份好简历 #
618590次浏览 8723人参与
# 在职场上，你最讨厌什么样的同事 #
5949次浏览 90人参与
# 硬件兄弟们 甩出你的华为奖状 #
78396次浏览 628人参与
# 你觉得第一学历对求职有影响吗？ #
17695次浏览 155人参与
牛客网
牛客企业服务