《算法竞赛进阶指南》 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;
}

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