《算法竞赛进阶指南》 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;
}
有向无环图最小路径点覆盖 待续
投递美团等公司10个岗位 >
字节跳动公司氛围 549人发布
