http://www.lydsy.com/JudgeOnline/problem.php?id=3532 (题目链接)
题意
给出$n$个数的数列,三个值$a[i],b[i],c[i]$。将其中一些数删掉,使得序列的$a[i]$的最长上升子序列至少减少$1$,删掉的数的$b[i]$和最小,在$b[i]$最小的情况下选$c[i]$排序后字典序最小的方案输出。
Solution
拆点,状态能够转移就连边,最小割。
用退流的思想求方案。按照$c[i]$从小到大枚举边,如果这条边满流且为必要边,那么退流即可。
所谓退流,就是把边$(u,v)$和$(v,u)$的残余流量清空,从$(u,S)$跑一遍最大流,从$(T,v)$跑一遍最大流就可以了。
这里我判断一条满流边能否在割集中是bfs判的,复杂度是$O(nm)$。
其实可以换成Tarjan,在残量网络中跑Tarjan求出SCC,如果$u$和$v$在同一个强联通分量中那么这条边$(u,v)$不能再割集中。呸,为什么判一条满流边能否在割集中这么麻烦还要Tarjan= =,直接利用最后一次$Dinic$求得的分层图判断一下就好了呀。。
呸,我在想什么= =,因为要退流,所以只能bfs,Tarjan或者是利用分层图都是邓的。。。
细节
数组开小。
代码
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
#define inf (1ll<<30)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std; const int maxn=2010;
int head[maxn],id[maxn],a[maxn],b[maxn],t[maxn],f[maxn],n,es,et,ans,cnt;
struct edge {int from,to,next,w;}e[maxn*maxn];
pair<int,int> c[maxn]; void link(int u,int v,int w) {
e[++cnt]=(edge){u,v,head[u],w};head[u]=cnt;
e[++cnt]=(edge){v,u,head[v],0};head[v]=cnt;
}
void Init() {
ans=t[0]=0,cnt=1;es=2*n+1,et=es+1;
memset(head,0,sizeof(head));
memset(f,0,sizeof(f));
} namespace Dinic {
int d[maxn],s,t;
bool bfs(int s,int t) {
memset(d,-1,sizeof(d));
queue<int> q;q.push(s);d[s]=0;
while (!q.empty()) {
int x=q.front();q.pop();
for (int i=head[x];i;i=e[i].next)
if (e[i].w && d[e[i].to]<0) d[e[i].to]=d[x]+1,q.push(e[i].to);
}
return d[t]>0;
}
int dfs(int x,int f) {
if (f==0 || x==t) return f;
int w,used=0;
for (int i=head[x];i;i=e[i].next) if (e[i].w && d[e[i].to]==d[x]+1) {
w=dfs(e[i].to,min(e[i].w,f-used));
used+=w;e[i].w-=w;e[i^1].w+=w;
if (used==f) return used;
}
if (!used) d[x]=-1;
return used;
}
int main(int x,int y) {
s=x,t=y;int flow=0;
while (bfs(x,y)) flow+=dfs(x,inf);
return flow;
}
} int main() {
int T;scanf("%d",&T);
while (T--) {
scanf("%d",&n);Init();
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<=n;i++) scanf("%d",&b[i]),id[i]=cnt+1,link(i,i+n,b[i]);
for (int i=1;i<=n;i++) scanf("%d",&c[i].first),c[i].second=i;
sort(c+1,c+1+n);
for (int i=1;i<=n;i++) {
f[i]=1;
for (int j=1;j<i;j++)
if (a[j]<a[i] && f[j]+1>f[i]) f[i]=f[j]+1;
if (f[i]==1) link(es,i,inf);
for (int j=1;j<i;j++)
if (a[j]<a[i] && f[j]+1==f[i]) link(j+n,i,inf);
ans=max(ans,f[i]);
}
for (int i=1;i<=n;i++) if (f[i]==ans) link(i+n,et,inf);
ans=Dinic::main(es,et);
for (int i=1;i<=n;i++) if (!e[id[c[i].second]].w) {
int j=id[c[i].second];
if (Dinic::bfs(e[j].from,e[j].to)) continue; //important
Dinic::main(e[j].from,es);
Dinic::main(et,e[j].to);
e[j].w=e[j^1].w=0;
t[++t[0]]=c[i].second;
}
sort(t+1,t+1+t[0]);
printf("%d %d\n",ans,t[0]);
for (int i=1;i<t[0];i++) printf("%d ",t[i]);printf("%d\n",t[t[0]]);
}
return 0;
}
【bzoj3532】 Sdoi2014—Lis的更多相关文章
-
【BZOJ3531】[Sdoi2014]旅行 树链剖分+动态开点线段树
[BZOJ3531][Sdoi2014]旅行 Description S国有N个城市,编号从1到N.城市间用N-1条双向道路连接,满足从一个城市出发可以到达其它所有城市.每个城市信仰不同的宗教,如飞天 ...
-
【BZOJ3529】[Sdoi2014]数表 莫比乌斯反演+树状数组
[BZOJ3529][Sdoi2014]数表 Description 有一张N×m的数表,其第i行第j列(1 < =i < =礼,1 < =j < =m)的数值为能同时整除i和 ...
-
【BZOJ-3532】Lis 最小割 + 退流
3532: [Sdoi2014]Lis Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 704 Solved: 264[Submit][Status] ...
-
【HDU3530】 [Sdoi2014]数数 (AC自动机+数位DP)
3530: [Sdoi2014]数数 Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 682 Solved: 364 Description 我们称一 ...
-
【转】关于LIS和一类可以用树状数组优化的DP 预备知识
原文链接 http://www.cnblogs.com/liu-runda/p/6193690.html 预备知识 DP(Dynamic Programming):一种以无后效性的状态转移为基础的算法 ...
-
【bzoj3531】 [SDOI2014]旅行
题目描述 S国有N个城市,编号从1到N.城市间用N-1条双向道路连接,满足从一个城市出发可以到达其它所有城市.每个城市信仰不同的宗教,如飞天面条神教.隐形独角兽教.绝地教都是常见的信仰.为了方便,我们 ...
-
【bzoj3529】 Sdoi2014—数表
μhttp://www.lydsy.com/JudgeOnline/problem.php?id=3529 (题目链接) 题意 多组询问,每次给出${n,m,a}$.求$${\sum_{i=1}^n\ ...
-
【bzoj3533】[Sdoi2014]向量集 线段树+STL-vector维护凸包
题目描述 维护一个向量集合,在线支持以下操作:"A x y (|x|,|y| < =10^8)":加入向量(x,y);"Q x y l r (|x|,|y| < ...
-
【bzoj3529】[Sdoi2014]数表 莫比乌斯反演+离线+树状数组
题目描述 有一张n×m的数表,其第i行第j列(1 <= i <= n ,1 <= j <= m)的数值为能同时整除i和j的所有自然数之和.给定a,计算数表中不大于a的数之和. ...
随机推荐
-
ural Cipher Message
Cipher Message Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Desc ...
-
iostat的深入理解
问题背景 iostat -xdm 1 通常用来查看机器磁盘IO的性能. 我们一般会有个经验值,比如,ioutil要小于80%, svctm要小于2ms. 前几天碰到一个奇怪的现象:有一台SSD机器,磁 ...
-
x位全排列(next_permutation)
擅长排列的小明 时间限制:1000 ms | 内存限制:65535 KB 难度:4 描述 小明十分聪明,而且十分擅长排列计算.比如给小明一个数字5,他能立刻给出1-5按字典序的全排列,如果你想 ...
-
HDU 4508 湫湫系列故事——减肥记I(全然背包)
HDU 4508 湫湫系列故事--减肥记I(全然背包) http://acm.hdu.edu.cn/showproblem.php?pid=4508 题意: 有n种食物, 每种食物吃了能获得val[i ...
-
企业架构研究总结(42)——企业架构与建模之ArchiMate详述(中)
2.4 技术层模型元素 技术层模型元素包括了企业在信息基础设施方面(企业中基本的软硬件环境,包括物理设备.系统软件等为信息化提供基本支持的设施)的各种概念元素,以及他们之间的关系.与应用层模型元素相类 ...
-
解决Fileupload 在IE 10 中需要双击的问题
方法来自于:https://code.google.com/p/primefaces/issues/detail?id=5355 the oncomplete event is working for ...
-
MySQL(十六)之MySQL用户管理
一.MySQL用户管理概述 MySQL是一个多用户的数据库,MYSQL的用户可以分为两大类: 超级管理员用户(root),拥有全部权限 普通用户,由root创建,普通用户只拥有root所分配的权限 二 ...
-
Vue项目用于Ios和Android端开发
起因 前公司商城App项目使用的是H5开发,有微信公众号.Ios和Android三个版本,H5版本是自己写的一套框架,已经用了有些年头了,承载不下不断涌现出的新需求.而Ios和Android端通过we ...
-
在Visual Studio 2013中安装Mysql for EntityFramework
1. 安装Visual Studio 20132. 下载mysql,安装mysql.3. 下载 mysql-for-visualstudio-1.2.7.msi, 下载链接:https://cdn.m ...
-
(11)模板语言-if判断
views.py from django.shortcuts import render,HttpResponse # Create your views here. def index(reques ...