[Bzoj1001][BeiJing2006]狼抓兔子(网络流/对偶图)
2024-10-19 03:29:07
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1001
看到大佬们都是对偶图过的,写了个最大流水过去了QAQ,网络流的无向图直接建双向边(不用建0边),然后跑dinic,最基本的dinic会被卡,可以简单优化一下。
有空学了对偶图在补,(个_个)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 6e6 + ;
const int inf = INT_MAX;
struct node {
int e, w, next;
}edge[maxn];
int head[maxn], len;
int d[maxn];
void init() {
memset(head, -, sizeof(head));
len = ;
}
void add(int s, int e, int w) {
edge[len].e = e;
edge[len].w = w;
edge[len].next = head[s];
head[s] = len++;
}
inline int read() {
int x = , f = ; char ch = getchar();
while (ch<'' || ch>'') { if (ch == '-')f = -; ch = getchar(); }
while (ch >= ''&&ch <= '') { x = x * + ch - ; ch = getchar(); }
return x * f;
}
bool bfs(int s, int e) {
queue<int>q;
memset(d, , sizeof(d));
d[s] = ;
q.push(s);
while (!q.empty()) {
int x = q.front(); q.pop();
for (int i = head[x]; i != -; i = edge[i].next) {
int y = edge[i].e;
if (edge[i].w && !d[y]) {
d[y] = d[x] + ;
q.push(y);
}
}
}
return d[e];
}
int dfs(int s, int e, int limit) {
if (s == e)
return limit;
int add, ans = ;
for (int i = head[s]; i != -; i = edge[i].next) {
int y = edge[i].e;
if (d[s] == d[y] - && edge[i].w && (add = dfs(y, e, min(edge[i].w, limit)))) {
edge[i].w -= add;
edge[i ^ ].w += add;
ans += add;
limit -= add;
if (!limit)
break;
}
}
if (ans)
return ans;
d[s] = -;
return ;
}
int dinic(int s, int e) {
int ans = , f;
while (bfs(s, e)) {
while (f = dfs(s, e, inf))
ans += f;
}
return ans;
}
int main() {
int n, m, z;
n = read(), m = read();
init();
for (int i = ; i <= n; i++)
for (int j = ; j < m; j++) {
z = read();
add(m*(i - ) + j, m*(i - ) + j + , z);
add(m*(i - ) + j + , m*(i - ) + j, z);
}
for (int i = ; i < n; i++)
for (int j = ; j <= m; j++) {
z = read();
add(m*(i - ) + j, m*i + j, z);
add(m*i + j, m*(i - ) + j, z);
}
for (int i = ; i < n; i++)
for (int j = ; j < m; j++) {
z = read();
add(m*(i - ) + j, m*i + j + , z);
add(m*i + j + , m*(i - ) + j, z);
}
printf("%d\n", dinic(, n*m));
//system("pause");
}
最新文章
- 浅谈android binder机制
- Docker on Microsoft Azure
- Java的静态导入
- 20个精美的免费 PSD 界面设计素材【免费下载】
- EL表达式从request和session中取值
- Java Cryptography Extension (JCE): 放开Java加密算法密钥最大长度16的限制
- C#命名空间“Microsoft.Office”中不存在类型或命名空间名称的终极解决方法
- [iOS 多线程 &; 网络 - 2.9] - ASI框架
- ZOJ2317-Nice Patterns Strike Back:矩阵快速幂,高精度
- day49
- Java线程如何返回数据
- springBoot系列教程05:fastjson的集成、配置及使用
- c++(排序二叉树线索化)
- 《Java编程的逻辑》终于上市了!
- knockoutjs关于ko.bindingHandlers的updata订阅
- Linux - 日志处理一
- 【ORACLE】oracl基本操作笔记
- CopyTransform
- 微信小程序底部导航Tabbar
- Android的方法数超过65535问题