#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define P 55
#define N 2050
#define INF (1<<30) using namespace std; int n,m,S,T,ss,tt,cnt=,tot=;
int head[N],d[N],p[N],qlc[P],qrc[P],qlr[P],qrr[P];
int map[P][P],sc[P],sr[P],r[P],c[P],dis[N];
int ans,tl;
struct Edge{ int a,b,v,cost,next; }e[*N];
void add(int a,int b,int v,int cost) {
e[++cnt].a = a;
e[cnt].b = b;
e[cnt].v = v;
e[cnt].cost = cost;
e[cnt].next = head[a];
head[a] = cnt;
} inline void add_Node(int a,int b,int vl,int vr,int cost) {
//printf("Node %d %d %d %d\n",a,b,vl,vr);
d[a] -= vl; d[b] += vl;
add(a,b,vr-vl,cost); add(b,a,,-cost);
}
void paul() {
ss = tot+; tt = tot+;
for (int _=;_<=tot;_++) {
if (d[_] < ) add(_,tt,-d[_],) , add(tt,_,,);
if (d[_] > ) add(ss,_, d[_],) , add(_,ss,,);
}
} #define cp e[i].v
#define B e[i].b bool SPFA() {
bool flag = false;
memset(p,,sizeof(p));
memset(dis,0x3f3f3f3f,sizeof(dis));
dis[ss] = ;
queue<int> q; q.push(ss);
while (!q.empty()) {
int u = q.front(); q.pop();
if (u == tt) flag = true;
for (int i=head[u];i;i=e[i].next)
if (cp > && dis[u] + e[i].cost < dis[B]) {
dis[B] = dis[u] + e[i].cost;
p[B] = i;
q.push(B);
}
}
return flag;
} void mcf() {
int g = p[tt] , flow = INF;
while (g) {
flow = min(flow , e[g].v);
g = p[ e[g].a ];
}
g = p[tt];
while (g) {
e[g ].v -= flow;
e[g^].v += flow;
ans += e[g].cost * flow;
g = p[ e[g].a ];
}
tl += flow;
} void init() {
memset(head,,sizeof(head));
memset(e,,sizeof(e));
memset(d,,sizeof(d)); //memset(qlr,0,sizeof(qlr));
//memset(qrr,0,sizeof(qrr));
//memset(qlc,0,sizeof(qlc));
//memset(qrc,0,sizeof(qrc)); memset(sc,,sizeof(sc));
memset(sr,,sizeof(sr));
memset(c,,sizeof(c));
memset(r,,sizeof(r));
memset(map,,sizeof(map));
cnt = ; tot = ;
S = ++tot; T = ++tot; add_Node(T,S,,INF,);
ans = tl = ;
} int main() {
#ifndef ONLINE_JUDGE
freopen("5.in","r",stdin);
#endif
while (~scanf("%d",&n)) {
init();
for (int i=;i<=n;i++) for (int j=;j<=n;j++) {
scanf("%d",&map[i][j]);
if (map[i][j]) sr[i]++ ,sc[j]++;
}
for (int i=;i<=n;i++) r[i] = ++tot , c[i] = ++tot;
for (int i=;i<=n;i++) {
scanf("%d%d",&qlr[i],&qrr[i]);
add_Node(S,r[i],sr[i],sr[i],); //³¬¼¶Ô´ --> µÚiÐÐ
add_Node(r[i],T,qlr[i],qrr[i],); //µÚiÐÐ --> ³¬¼¶»ã
}
for (int i=;i<=n;i++) {
scanf("%d%d",&qlc[i],&qrc[i]);
add_Node(S,c[i],sc[i],sc[i],); //³¬¼¶Ô´ --> µÚiÁÐ
add_Node(c[i],T,qlc[i],qrc[i],); //µÚiÁÐ --> ³¬¼¶»ã
}
for (int i=;i<=n*n/;i++) {
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if (map[x1][y1] == map[x2][y2]) continue;
if (!map[x1][y1]) swap(x1,x2) , swap(y1,y2);
if (x1 == x2) add_Node(c[y1],c[y2],,,); //Èç¹ûÔÚͬһÐÐ ¾ÍÔÚÁÐÖ®¼äÁ¬±ß
if (y1 == y2) add_Node(r[x1],r[x2],,,); //Èç¹ûÔÚͬһÁÐ ¾ÍÔÚÐÐÖ®¼äÁ¬±ß
}
paul(); //²¹ÉÏËùÓвðµÄ±ß //for (int i=2;i<=cnt;i+=2) if (e[i].v) printf("%d %d %d %d\n",e[i].a,e[i].b,e[i].v,e[i].cost); while (SPFA())
mcf();
//for (int i=3;i<=cnt;i+=2) if (e[i].v) printf("%d %d %d\n",e[i].b,e[i].a,e[i].v); for (int i=head[ss];i;i=e[i].next) if (e[i].v) ans = -;//ÅжÏÊÇ·ñÓнâ
if (ans == -) puts("-1"); else printf("%d\n",ans);
}
return ;
}
UvaL-7670 上下界可行费用流的更多相关文章
-
【UVALive - 5131】Chips Challenge(上下界循环费用流)
Description A prominent microprocessor company has enlisted your help to lay out some interchangeabl ...
-
【BZOJ-4213】贪吃蛇 有上下界的费用流
4213: 贪吃蛇 Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 58 Solved: 24[Submit][Status][Discuss] Desc ...
-
BZOJ2055 80人环游世界 网络流 费用流 有源汇有上下界的费用流
https://darkbzoj.cf/problem/2055 https://blog.csdn.net/Clove_unique/article/details/54864211 ←对有上下界费 ...
-
BZOJ 2055: 80人环游世界(有上下界的费用流)
题面 Time Limit: 10 Sec Memory Limit: 64 MB Submit: 693 Solved: 434 [Submit][Status][Discuss] Descript ...
-
【上下界网络流 费用流】bzoj2055: 80人环游世界
EK费用流居然写错了…… Description 想必大家都看过成龙大哥的<80天环游世界>,里面的紧张刺激的打斗场面一定给你留下了深刻的印象.现在就有这么 一个80人的团 ...
-
Codeforces Gym 101190 NEERC 16 .D Delight for a Cat (上下界的费用流)
ls是一个特别堕落的小朋友,对于n个连续的小时,他将要么睡觉要么打隔膜,一个小时内他不能既睡觉也打隔膜 ,因此一个小时内他只能选择睡觉或者打隔膜,当然他也必须选择睡觉或打隔膜,对于每一个小时,他选择睡 ...
-
BZOJ 3876 支线剧情 有源汇有上下界最小费用可行流
题意: 给定一张拓扑图,每条边有边权,每次只能从第一个点出发沿着拓扑图走一条路径,求遍历所有边所需要的最小边权和 分析: 这道题乍一看,可能会想到什么最小链覆盖之类的,但是仔细一想,会发现不行,一是因 ...
-
BZOJ 2055 80人环游世界 有上下界最小费用可行流
题意: 现在有这么一个m人的团伙,也想来一次环游世界. 他们打算兵分多路,游遍每一个国家. 因为他们主要分布在东方,所以他们只朝西方进军.设从东方到西方的每一个国家的编号依次为1...N.假若第 ...
-
[BZOJ2055]80人环游世界 有上下界最小费用最大流
2055: 80人环游世界 Time Limit: 10 Sec Memory Limit: 64 MB Description 想必大家都看过成龙大哥的<80天环游世界>,里面 ...
随机推荐
-
linux下tomcat服务的启动、关闭与错误跟踪
linux下tomcat服务的启动.关闭与错误跟踪,远程连接到服务器以后,通常通过以下几种方式启动关闭tomcat服务: 1).启动tomcat服务 进入tomcat主目录下的bin目录,然后执行如下 ...
-
一个IT人士的个人经历,给迷失方向的朋友
这些日子我一直在写一个实时操作系统内核,已有小成了,等写完我会全部公开,希望能够为国内IT的发展尽自己一份微薄的力量.最近看到很多学生朋友和我当年一样没有方向 ,所以把我的经历写出来与大家共勉,希望能 ...
-
web常见效果之轮播图
轮播图的展示效果是显而易见: HTML代码如下 <!DOCTYPE html> <html> <head> <meta charset="UTF-8 ...
-
第十章:Python の 网络编程基础(二)
本課主題 Python中的作用域补充 socketserver 源码 线程的介绍和操作实战 进程的介绍和操作实战 协程的介绍和操作实战 本周作业 Python中的作用域补充 Python世界里沒有块级 ...
-
python的加、减、乘、除、取整、取余计算
加法: 输入以下代码: >>>1+1 >>>1.0+1 减法: 输入以下代码: >>>1-2 >>>1.0-2 乘法: 输入以下 ...
-
java某些基础知识点整理
1. \n换行 \r回车 \"双引号 \\反斜杠 2.Java语言提供了八种基本类型.六种数字类型(四个整数型,两个浮点型),一种字符类型,还有一种布尔型. byte: byte 数据类型是 ...
-
DevExpress.Mvvm.Free
DevExpress MVVM Framework is a set of components helping to work in the Model-View-ViewModel pattern ...
-
org.apache.ibatis.binding.BindingException: Parameter &#39;idList&#39; not found解决办法
https://blog.csdn.net/qq_28379809/article/details/83342196 问题描述 使用Mybatis查询数据库报错: org.apache.ibatis. ...
-
cacti+CentOS6.5
系统版本:CentOS6.5 软件版本:cacti-0.88f 需要预安装的软件有以下几种,可以通过yum安装全部 yum -y install net-snmp* yum -y install op ...
-
javascript中 try catch finally 的使用
例一:function message(){ try { adddlert("Welcome guest!") } catch(err) { txt="此页面存在一个错误 ...