技术标签： 最大流最小割 -------图论------- 上下界网络流
传送门：bzoj1458
很直观地想到带上下界最小可行流。
然而直接容斥跑最大流即可(好写多了！)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define T 201
#define inf 0x7fffffff
inline int read()
{
char ch=getchar();
int f=1,x=0;
while(!(ch>='0'&&ch<='9')){
if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
using namespace std;
int n,m,K,cnt=1,tot,ans;
int l[105],c[105],a[105],b[105];
bool mp[105][105];
int q[205],h[205],head[205],cur[205];
struct data{
int to,next,v;}e[100001];
void ins(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;}
void insert(int u,int v,int w)
{
ins(u,v,w);ins(v,u,0);}
bool bfs()
{
int t=0,w=1;
for(int i=0;i<=T;i++)h[i]=-1;
q[0]=0;h[0]=0;
while(t!=w)
{
int now=q[t];t++;
for(int i=head[now];i;i=e[i].next)
if(e[i].v&&h[e[i].to]==-1)
{
h[e[i].to]=h[now]+1;
q[w++]=e[i].to;
}
}
if(h[T]==-1)return 0;
return 1;
}
int dfs(int x,int f)
{
if(x==T)return f;
int w,used=0;
for(int i=cur[x];i;i=e[i].next)
{
if(e[i].v&&h[e[i].to]==h[x]+1)
{
w=f-used;
w=dfs(e[i].to,min(e[i].v,w));
e[i].v-=w;
if(e[i].v)cur[x]=i;
e[i^1].v+=w;
used+=w;if(used==f)return f;
}
}
if(!used)h[x]=-1;
return used;
}
void dinic()
{
while(bfs()){
for(int i=0;i<=T;i++)cur[i]=head[i];ans+=dfs(0,inf);}}
int main()
{
m=read();n=read();K=read();
int x,y;
for(int i=1;i<=m;i++)
l[i]=n-read();
for(int i=1;i<=n;i++)
c[i]=m-read();
for(int i=1;i<=K;i++)
{
x=read();y=read();
mp[x][y]=1;
a[x]++;b[y]++;
if(a[x]>l[x]){
printf("JIONG!");return 0;}
if(b[y]>c[y]){
printf("JIONG!");return 0;}
}
tot=n*m-K;
for(int i=1;i<=m;i++)
insert(0,i,l[i]-a[i]);
for(int i=1;i<=n;i++)
insert(m+i,T,c[i]-b[i]);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
if(!mp[i][j])insert(i,j+m,1);
dinic();
printf("%d",tot-ans);
return 0;
}
文章浏览阅读102次。问题：[判断题] 计算机的工作组名或域名、计算机名等区分计算机特征的配置不得随意修改，但可以自行修改计算机的IP地址。()A . 正确B . 错误工商专网为非涉密网，与政务内网实现数据共享，可以直接相连。() 正确。 错误。上官夫妇目前均刚过35岁，打算20年后即55岁时退休，估计夫妇俩退休后第一年的生活费用为8万元(退休后每年初从退休金中取出当年的生活费用)。考虑到通货膨胀的因素，夫妇俩每年的..._域名能否替代计算机名
文章浏览阅读474次。具体的写法：:-moz-placeholder { /* Mozilla Firefox 4 to 18 */ color: #fff; font-size: 0.56rem;opacity: 0.8;}::-moz-placeholder { /* Mozilla Firefox 19+ */ color: #fff; font-size: 0.56rem_input中placeholder的字体颜色
文章浏览阅读1.3w次，点赞24次，收藏144次。文章目录为什么使用工作流引擎？不使用工作流存在以下问题工作流优缺点什么是工作流引擎尝试自己构建工作流引擎有哪些选型方案呢基于bpmn标准进行流程定义国产自定义如何使用SnakerFlow工作流以请假流程来看下数据库中数据流转情况初始状态员工发起请假申请常见功能流程标题发起申请我的发起我的待办我的已办催办转办驳回撤回抄送加签会签或签为什么使用工作流引擎？反证法，如果不使用工作流引擎，先以请假流程举例，从头开始开发流程的业务逻辑：（来看看会出现哪些问题？使用工作流能解决哪些问题？又会带来什么问题？）一_工作流引擎是什么
文章浏览阅读435次。访问解题链接去访问题目,可以进行答题。根据web题一般解题思路去解答此题。看源码，请求，响应等。提交与题目要求一致的内容即可返回flag。然后提交正确的flag即可得分。web题主要考察SQL注入，XSS等相关知识。涉及方向较多。此题主要涉及源码审计，MySQL相关的知识。flag格式 CTF{}我们访问网站之后 出现这个我们要先进行查看源码发现了 sourc..._preg_match(/.$arrreq./is,$strvalue)==1
文章浏览阅读90次。1、SpringMVC的返回JSON数据 到目前为止我们编写的所有Controller的方法的返回值都是String类型，但是大家应该都知道，我们有时候数据传递特别是在ajax中，我们返回的数据经常需要使用json，那么如何来保证返回的数据的是json格式呢？使用@ResponseBody注解pom.xml<?xml version="1.0" encoding="UTF-8"?><project xmlns="http://maven.apache.org/POM/4.0.0_prehandle requestbody
文章浏览阅读550次。开发所需工具类开发所需jar具体的代码不贴了，说明下PayConfigUtil中的参数APP_ID和APP_SECRET在公众平台MCH_ID和API_KEY在商户平台,其中API_KEY是自己设置的，并不是自动生成的。Controlle..._微信支付对应示例 java appid secret
文章浏览阅读2.5w次，点赞23次，收藏17次。最近遇到快速访问的文件夹右键无法取消固定，不管怎么试都删不掉，最后我尝试了把快速访问恢复默认，解决了这个问题具体方法：找到快速访问的存储目录是这里，大家可以应对自己所用环境修改用户名：C:\Users\用户名\AppData\Roaming\Microsoft\Windows\Recent\AutomaticDestinations删除路径中的所有文件，快速访问就会重置到最初的状态！在..._automaticdestinations文件夹里的文件删不掉
文章浏览阅读2.3k次，点赞18次，收藏17次。基于vue.js宠物医院挂号系统设计与实现(uni-app框架+PHP后台) 研究背景和意义、国内外现状主人的满意度和宠物的健康至关重要。因此，开发一套基于vue.js的宠物医院挂号系统，利用uni-app框架和PHP后台，能够提供方便快捷的预约挂号服务，改善宠物医疗服务的质量和用户体验，具有重要的研究意义和实际应用价值。因此，研究开发一套基于vue.js的宠物医院挂号系统，能够填补国内外研究空白，提升宠物医疗服务的质量和用户体验，具有重要的研究意义和实际应用价值。专注大学生毕业设计教育和辅导。_宠物挂号系统 php
文章浏览阅读131次。先离线，离散化在线段树维护区间和以及数量#include <bits/stdc++.h>using namespace std;///#pragma GCC optimize(2)#define Mode 1000000007const int N = 1<<17;struct node{ long long Sum; long lo..._hdoj 5624
文章浏览阅读63次。在Blend中，有一个功能，Make into control---通过它可以方便的自定义各种个性化的控件，例如把图片，文本，或者几何形状等等变成Button控件。当然，不只是Button可以变，还有各种各样的控件，几乎包括了所以的基本控件，而它们的外观到底是什么样，那就取决于你的创造力了。今天，就继续练习下这个功能的使用，跟着我一起做吧，你会发现blend真的很棒，当然，开始的时候可能会觉得过程...
文章浏览阅读7k次，点赞2次，收藏3次。'node-gyp-build' is not recognized as an internal or external command, operable program or batch file.npm ERR! gyp verb `which` failed Error: not found: python2_node-gyp-build
文章浏览阅读2.8k次。Python内置了整数、复数、浮点数三种数字类型。整数整数是没有小数部分的数值，与数学上的一样：>>> 11>>> -1-1整数没有大小限制，只要你的内存足够大，就可以创建任意大小的整数：>>> 111111111111111111111111111111111111111111111111111111111111111111111111111..._python 语言的浮点数可以不带小数部分