题目链接: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");
}

最新文章

  1. 浅谈android binder机制
  2. Docker on Microsoft Azure
  3. Java的静态导入
  4. 20个精美的免费 PSD 界面设计素材【免费下载】
  5. EL表达式从request和session中取值
  6. Java Cryptography Extension (JCE): 放开Java加密算法密钥最大长度16的限制
  7. C#命名空间“Microsoft.Office”中不存在类型或命名空间名称的终极解决方法
  8. [iOS 多线程 &amp; 网络 - 2.9] - ASI框架
  9. ZOJ2317-Nice Patterns Strike Back:矩阵快速幂,高精度
  10. day49
  11. Java线程如何返回数据
  12. springBoot系列教程05:fastjson的集成、配置及使用
  13. c++(排序二叉树线索化)
  14. 《Java编程的逻辑》终于上市了!
  15. knockoutjs关于ko.bindingHandlers的updata订阅
  16. Linux - 日志处理一
  17. 【ORACLE】oracl基本操作笔记
  18. CopyTransform
  19. 微信小程序底部导航Tabbar
  20. Android的方法数超过65535问题

热门文章

  1. AtCoder AGC014E Blue and Red Tree (启发式合并)
  2. Bzoj3073Journeys
  3. Springdata-Jpa学习笔记
  4. 尚学堂requireJs课程---1、作用域回顾
  5. 在linux下通过ssh运行X图形软件
  6. PHPstrom中关闭提示信息
  7. ping包的checksum校验和
  8. koa 基础(十八)es6中的类、静态方法、继承
  9. Linux性能分析之上下文切换
  10. mips调试