http://www.lydsy.com/JudgeOnline/problem.php?id=3532
如果没有字典序的限制,那么DP拆点最小割即可
加上字典序的限制:
按c从小到大枚举最小割边集中的边,去掉这条边对网络的影响,继续枚举直至获得最小割边集
判断是不是最小割边集中的边:
在残量网络中边的起点和终点不连通
注:最小割边集中的边一定满流,但满流边不一定是最小割边集中的边
如下图所示,流量为1和3的两条边满流,但最小割边集为流量为4的那条边
去掉一条边对网络的影响:
边:u-->v
这条边的流量和反向弧的流量置为0
在残量网络上,汇点向v跑一遍最大流,u向源点跑一遍最大流
判断已经得到了最小割中的所有边:
残量网络上,源点和汇点不连通
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> using namespace std; #define N 1410
#define M 520000
const int inf=2e9; int n;
int a[N],b[N],c[N]; int f[N]; int tot;
int front[N],nxt[M<<],to[M<<],val[M<<],from[M<<];
int lev[N],num[N];
int path[N];
int cur[N]; int src,decc; int id[N];
bool use[N];
int cnt[N]; int all; int ans[N]; bool vis[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int u,int v,int w)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; from[tot]=u; val[tot]=w;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; from[tot]=v; val[tot]=;
// cout<<u<<' '<<v<<' '<<w<<'\n';
} bool bfs()
{
queue<int>q;
for(int i=;i<=all;++i) lev[i]=all;
q.push(decc);
lev[decc]=;
int now,t;
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=front[now];i;i=nxt[i])
{
t=to[i];
if(lev[t]==all && val[i^])
{
lev[t]=lev[now]+;
q.push(t);
}
}
}
return lev[src]!=all;
} int augment()
{
int now=decc,flow=inf;
int i;
while(now!=src)
{
i=path[now];
flow=min(flow,val[i]);
now=from[i];
}
now=decc;
while(now!=src)
{
i=path[now];
val[i]-=flow;
val[i^]+=flow;
now=from[i];
}
return flow;
} void isap()
{
int flow=;
if(!bfs()) return ;
memset(num,,sizeof(num));
for(int i=;i<=all;++i) num[lev[i]]++,cur[i]=front[i];
int now=src,t;
while(lev[src]<all)
{
if(now==decc)
{
flow+=augment();
now=src;
}
bool advanced=false;
for(int i=cur[now];i;i=nxt[i])
{
t=to[i];
if(lev[t]==lev[now]- && val[i])
{
advanced=true;
path[t]=i;
cur[now]=i;
now=t;
break;
}
}
if(!advanced)
{
int mi=all;
for(int i=front[now];i;i=nxt[i])
if(val[i]) mi=min(mi,lev[to[i]]);
if(!--num[lev[now]]) break;
num[lev[now]=mi+]++;
cur[now]=front[now];
if(now!=src) now=from[path[now]];
}
}
// cout<<flow<<'\n';
} void build()
{
src=; decc=(n<<|)+;
int mx,max_len=;
for(int i=n;i;--i)
{
mx=;
for(int j=i+;j<=n;++j)
if(a[j]>a[i]) mx=max(mx,f[j]);
f[i]=mx+;
max_len=max(max_len,f[i]);
}
tot=;
memset(front,,sizeof(front));
for(int i=;i<=n;++i)
{
id[i]=tot+;
add(i<<,i<<|,b[i]);
}
for(int i=;i<=n;++i)
if(f[i]==max_len) add(src,i<<,inf);
for(int i=;i<=n;++i)
if(f[i]==) add(i<<|,decc,inf);
for(int i=;i<=n;++i)
for(int j=i+;j<=n;++j)
if(a[j]>a[i] && f[i]==f[j]+) add(i<<|,j<<,inf);
} bool find(int u,int v)
{
memset(vis,false,sizeof(vis));
queue<int>q;
q.push(u);
vis[u]=true;
int now,t;
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=front[now];i;i=nxt[i])
{
if(!val[i]) continue;
t=to[i];
if(!vis[t])
{
vis[t]=true;
q.push(t);
}
}
}
return vis[v];
} void solve()
{
int sum=,num=;
int mi;
c[]=inf;
memset(use,false,sizeof(use));
while()
{
mi=;
for(int i=;i<=n;++i)
if(!val[id[i]] && !use[i] && c[mi]>c[i]) mi=i;
use[mi]=true;
if(find(from[id[mi]],to[id[mi]])) continue;
ans[++num]=mi;
sum+=b[mi];
val[id[mi]]=val[id[mi]+]=;
src=all; decc=mi<<|;
isap();
src=mi<<; decc=;
isap();
src=all; decc=;
if(!bfs()) break;
}
cout<<sum<<' '<<num<<'\n';
sort(ans+,ans+num+);
for(int i=;i<num;++i) cout<<ans[i]<<' ';
cout<<ans[num]<<'\n';
} int main()
{
int T;
read(T);
while(T--)
{
read(n);
all=(n<<|)+;
for(int i=;i<=n;++i) read(a[i]);
for(int i=;i<=n;++i) read(b[i]);
for(int i=;i<=n;++i) read(c[i]);
build();
isap();
solve();
}
}
3532: [Sdoi2014]Lis
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 977 Solved: 362
[Submit][Status][Discuss]
Description
给定序列A,序列中的每一项Ai有删除代价Bi和附加属性Ci。请删除若
干项,使得4的最长上升子序列长度减少至少1,且付出的代价之和最小,并输出方案。
如果有多种方案,请输出将删去项的附加属性排序之后,字典序最小的一种。
Input
输入包含多组数据。
输入的第一行包含整数T,表示数据组数。接下来4*T行描述每组数据。
每组数据的第一行包含一个整数N,表示A的项数,接下来三行,每行N个整数A1..An,B1.,Bn,C1..Cn,满足1 < =Ai,Bi,Ci < =10^9,且Ci两两不同。
Output
对每组数据,输出两行。第一行包含两个整数S,M,依次表示删去项的代价和与数量;接下来一行M个整数,表示删去项在4中的的位置,按升序输出。
Sample Input
6
3 4 4 2 2 3
2 1 1 1 1 2
6 5 4 3 2 1
Sample Output
2 3 6
解释:删去(A2,43,A6),(A1,A6),(A2,43,44,A5)等都是合法的方案,但
{A2,43,A6)对应的C值的字典序最小。
HINT
1 < =N < =700 T < =5
bzoj千题计划141:bzoj3532: [Sdoi2014]Lis的更多相关文章
-
bzoj千题计划300:bzoj4823: [Cqoi2017]老C的方块
http://www.lydsy.com/JudgeOnline/problem.php?id=4823 讨厌的形状就是四联通图 且左右各连一个方块 那么破坏所有满足条件的四联通就好了 按上图方式染色 ...
-
bzoj千题计划205:bzoj3529: [Sdoi2014]数表
http://www.lydsy.com/JudgeOnline/problem.php?id=3529 有一张n*m的数表,其第i行第j列(1 < =i < =n,1 < =j & ...
-
bzoj千题计划196:bzoj4826: [Hnoi2017]影魔
http://www.lydsy.com/JudgeOnline/problem.php?id=4826 吐槽一下bzoj这道题的排版是真丑... 我还是粘洛谷的题面吧... 提供p1的攻击力:i,j ...
-
bzoj千题计划280:bzoj4592: [Shoi2015]脑洞治疗仪
http://www.lydsy.com/JudgeOnline/problem.php?id=4592 注意操作1 先挖再补,就是补的范围可以包含挖的范围 SHOI2015 的题 略水啊(逃) #i ...
-
bzoj千题计划177:bzoj1858: [Scoi2010]序列操作
http://www.lydsy.com/JudgeOnline/problem.php?id=1858 2018 自己写的第1题,一遍过 ^_^ 元旦快乐 #include<cstdio> ...
-
bzoj千题计划317:bzoj4650: [Noi2016]优秀的拆分(后缀数组+差分)
https://www.lydsy.com/JudgeOnline/problem.php?id=4650 如果能够预处理出 suf[i] 以i结尾的形式为AA的子串个数 pre[i] 以i开头的形式 ...
-
bzoj千题计划316:bzoj3173: [Tjoi2013]最长上升子序列(二分+树状数组)
https://www.lydsy.com/JudgeOnline/problem.php?id=3173 插入的数是以递增的顺序插入的 这说明如果倒过来考虑,那么从最后一个插入的开始删除,不会对以某 ...
-
bzoj千题计划304:bzoj3676: [Apio2014]回文串(回文自动机)
https://www.lydsy.com/JudgeOnline/problem.php?id=3676 回文自动机模板题 4年前的APIO如今竟沦为模板,,,╮(╯▽╰)╭,唉 #include& ...
-
bzoj千题计划292:bzoj2244: [SDOI2011]拦截导弹
http://www.lydsy.com/JudgeOnline/problem.php?id=2244 每枚导弹成功拦截的概率 = 包含它的最长上升子序列个数/最长上升子序列总个数 pre_len ...
随机推荐
-
linQ学习笔记之三高级语句
linq语句查询执行的时机 第一步获取数据源 int [] obejct = new int[]{1,2,3,4,5,6,7,8,9} 第二步定义查询 var even = numbers.where ...
-
学习资料 数据查询语言DQL
数据查询语言DQL介绍及其应用: 查询是SQL语言的核心,SQL语言只提供唯一一个用于数据库查询的语句,即SELECT语句.用于表达SQL查询的SELECT语句是功能最强也是最复杂的SQL语句,它提供 ...
-
分布式文件系统FastDFS设计原理
原文地址: http://blog.chinaunix.net/uid-20196318-id-4058561.html FastDFS是一个开源的轻量级分布式文件系统,由跟踪服务器(tracker ...
-
android升级软件版本号,您安装后的新版本号,成功安装画面没有出现,或直接回到桌面
Intent intent = new Intent(Intent.ACTION_VIEW); intent.addFlags(Intent.FLAG_ACTIVITY_NEW_TASK); //an ...
-
浅谈Django的生命周期和CBF和FBC
Django的生命周期和CBF和FBC 对于所有的web框架来说本质就是一个socket服务端,浏览器是socket客户端,客户端和服务端通信,字符串(Http协议):请求头和请求体 响应头+响应体 ...
-
X5 Blink下文字自动变大
在X5 Blink中,页面排版时会主动对字体进行放大,会检测页面中的主字体,当某一块的字体在我们的判定规则中,认为字体的字号较小,并且是页面中的主要字体,就会采用主动放大的操作.这显然不是我们想要的. ...
-
Linux 文件目录解释
/bin:bin是binary(二进制)的缩写.这个目录是对UNIX系统习惯的沿袭,存放着使用者最经常使用的命令.例如:cp,ls,cat. /boot:这里存放的是启动LINUX时使用的一些核心文件 ...
-
Scala(二) —— 函数
try 表达式 var result = try{ Integer.parseInt("dog") }catch{ case _ => 0 }finally{ println ...
-
生信基础知识【04】GO和pathway分析
非原创 参考资料: 一文掌握GO和pathway分析 - 生物信息学讨论版 -丁香园论坛http://www.dxy.cn/bbs/thread/34904124#34904124 GO富集 GO是G ...
-
通过wlst工具创建weblogic11g域单节点包括服务与被管服务
1:创建域(1)节点一执行 export MV_HOME=/home/wzh/Oracle/Middleware export WL_HOME=$MV_HOME/wlserver_10. export ...