BZOJ 4823 老C的方块
2024-09-05 07:28:36
把格子分成四类 第一类是蓝线左右的相邻两个格子 第二类为与蓝线左边格子相邻的点 第三类为与蓝线右边格子相邻的点
建边就S朝第二类每个点建边 第二类每个点朝其相邻的第一类建边 第一类从左格子朝右格子建边 第一类朝与其相邻的第三类建边 第三类朝T建边
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef int JQK;
const int dir[][] = { , -, -, , , , , };
struct node {
int x, y, w, color;
} p[];
int n, m;
map<pair<int, int>, int> mp;
namespace dinic {
const int MAXN = ;
const int MAXM = ;
const int INF = ;
int Head[MAXN], cur[MAXN], lev[MAXN], to[MAXM << ], nxt[MAXM << ], ed = ;
int S, T, MAXP;
JQK f[MAXM << ];
inline void addedge(int u, int v, JQK cap) {
to[++ed] = v;
nxt[ed] = Head[u];
Head[u] = ed;
f[ed] = cap;
to[++ed] = u;
nxt[ed] = Head[v];
Head[v] = ed;
f[ed] = ;
return;
}
inline bool BFS() {
int u;
for (int i = ; i <= MAXP + ; i++) {
lev[i] = -;
}
//memset(lev, -1, sizeof(lev));
queue<int>q;
lev[S] = ;
q.push(S);
while (q.size()) {
u = q.front();
q.pop();
for (int i = Head[u]; i; i = nxt[i])
if (f[i] && lev[to[i]] == -) {
lev[to[i]] = lev[u] + ;
q.push(to[i]);
/*
if (to[i] == T)
{
return 1;
}
magic one way optimize
*/
}
}
for (int i = ; i <= MAXP + ; i++) {
cur[i] = Head[i];
}
//memcpy(cur, Head, sizeof Head);
return lev[T] != -;
}
inline JQK DFS(int u, JQK maxf) {
if (u == T || !maxf) {
return maxf;
}
JQK cnt = , tem;
for (int &i = cur[u]; i; i = nxt[i])
if (f[i] && lev[to[i]] == lev[u] + ) {
tem = DFS(to[i], min(maxf, f[i]));
maxf -= tem;
f[i] -= tem;
f[i ^ ] += tem;
cnt += tem;
if (!maxf) {
break;
}
}
if (!cnt) {
lev[u] = -;
}
return cnt;
}
JQK Dinic() {
JQK ans = ;
while (BFS()) {
ans += DFS(S, INF);
}
return ans;
}
void init(int SS, int TT) {
for (int i = ; i <= MAXP + ; i++) {
Head[i] = ;
}
ed = ;
S = SS;
T = TT;
return;
}
void work() {
for (int i = ; i <= n; i++) {
if (p[i].color == ) {
addedge(i, T, p[i].w);
} else if (p[i].color == ) {
addedge(S, i, p[i].w);
} else if (p[i].color == ) {
for (int j = ; j < ; j++) {
int dx = p[i].x + dir[j][];
int dy = p[i].y + dir[j][];
int aim = mp[make_pair(dx, dy)];
if (aim == ) {
continue;
} else if (p[aim].color == ) {
addedge(aim, i, INF);
} else if (p[aim].color == ) {
addedge(i, aim, min(p[aim].w, p[i].w));
}
}
} else {
for (int j = ; j < ; j++) {
int dx = p[i].x + dir[j][];
int dy = p[i].y + dir[j][];
int aim = mp[make_pair(dx, dy)];
if (aim == ) {
continue;
} else if (p[aim].color == ) {
addedge(i, aim, INF);
}
}
}
}
printf("%d\n", Dinic());
}
}
int get_color(int x, int y) {
if (x & ) {
return y % == || y % == ;
} else {
return y % == || y % == ;
}
}
int main() {
int r, c;
int s, t;
int x, y, w;
while (scanf("%d %d %d", &c, &r, &n) == ) {
mp.clear();
for (int i = ; i <= n; i++) {
scanf("%d %d %d", &y, &x, &w);
p[i].x = x, p[i].y = y, p[i].w = w;
mp[make_pair(x, y)] = i;
if ((x + y + ) & ) {
p[i].color = get_color(x, y) ? : ;
} else {
p[i].color = get_color(x, y) ? : ;
}
//cout << p[i].color << endl;
}
dinic::MAXP = n + ;
dinic::init(n + , n + );
dinic::work();
}
return ;
}
最新文章
- REDHAT一总复习1 ssh配置 禁用root用户SSH连接
- 嵌入式系统上实现GPS全球定位功能
- MSSQL获得表的字段名称及其参数
- windows phone listbox虚拟化（下）
- MVC 依赖注入/控制反转
- [PWA] Caching with Progressive libraries
- 使用SevenZipSharp出现“Can not load 7-zip library or internal COM error! Message: DLL file does not exist.”的解决方案
- 201521123052《Java程序设计》第9周学习总结
- mac的terminal快捷键
- selenium+unittest自动化测试
- Microsoft Visual Studio Community 2017 修改新建项目的默认位置
- 转载 [ZooKeeper.net] 3 ZooKeeper的分布式锁
- MTK 屏幕旋转90度
- 查找->动态查找表->哈希表
- Spring Boot 2 (三)：Spring Boot 2 相关开源软件
- 100道Java基础面试题
- JQ 确定与取消弹出框，选择确定执行Ajax
- 「Vue」vue cli3中axios的基本用法
- jquery解析XML及获取XML节点名称
- js二级联动