首页 > 代码库 > 3532: [Sdoi2014]Lis 最小字典序最小割
3532: [Sdoi2014]Lis 最小字典序最小割
3532: [Sdoi2014]Lis
Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 865 Solved: 311
[Submit][Status][Discuss]
Description
给定序列A,序列中的每一项Ai有删除代价Bi和附加属性Ci。请删除若
干项,使得4的最长上升子序列长度减少至少1,且付出的代价之和最小,并输出方案。
如果有多种方案,请输出将删去项的附加属性排序之后,字典序最小的一种。
这题难点在如何求一组最小字典序最小的最小割。
一条边是一种割集中的一条边当且仅当它在任何最大流方案中都是满流。
即它当前满流且从这条边的出点到入点找不到增广路。
当确定一条边必须在边集中后,从出点向S增广,从T向入点增广,再把容量清零,相当于把这条边删掉。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<queue>#define ll long long#define inf 0x3f3f3f3f#define N 1405#define M 1000005using namespace std;vector<int>ss;int head[N],ver[M],nxt[M],f[M],tot;void add(int a,int b,int c){ tot++;nxt[tot]=head[a];head[a]=tot;ver[tot]=b;f[tot]=c; tot++;nxt[tot]=head[b];head[b]=tot;ver[tot]=a;f[tot]=0;return ;}queue<int>q;int ch[N];int S,T;bool tell(){ memset(ch,-1,sizeof(ch)); q.push(S);ch[S]=0; while(!q.empty()) { int tmp=q.front();q.pop(); for(int i=head[tmp];i;i=nxt[i]) { if(f[i]&&ch[ver[i]]==-1) { ch[ver[i]]=ch[tmp]+1; q.push(ver[i]); } } } return ch[T]!=-1;}ll zeng(int a,int b){ if(a==T)return b; int r=0; for(int i=head[a];i!=0&&b>r;i=nxt[i]) { if(f[i]&&ch[ver[i]]==ch[a]+1) { int t=zeng(ver[i],min(f[i],b-r)); f[i]-=t;f[i^1]+=t;r+=t; } } if(!r)ch[a]=-1; return r;}ll dinic(){ ll r=0,t; while(tell()) { while(t=zeng(S,inf)) { r+=t; } } return r;}int n,a[N],b[N],c[N];int p[N],dp[N];bool cmp(int x,int y){ return c[x]<c[y];}int main(){ int cas; scanf("%d",&cas); while(cas--) { memset(head,0,sizeof(head)); memset(dp,0,sizeof(dp)); ss.clear(); scanf("%d",&n);tot=1;// i i*2 i*2+1 for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++)scanf("%d",&b[i]); for(int i=1;i<=n;i++)scanf("%d",&c[i]),add(i,i+n,b[i]); for(int i=1;i<=n;i++)p[i]=i; sort(p+1,p+n+1,cmp);int mx=0; for(int i=1;i<=n;i++) { dp[i]=1; for(int j=1;j<i;j++) { if(a[i]>a[j])dp[i]=max(dp[i],dp[j]+1); } mx=max(mx,dp[i]); } S=0;T=2*n+1; for(int i=1;i<=n;i++)if(dp[i]==mx)add(i+n,T,inf); for(int i=1;i<=n;i++)if(dp[i]==1)add(S,i,inf); for(int i=1;i<=n;i++) { for(int j=1;j<i;j++) { if(a[i]>a[j]&&dp[i]==dp[j]+1) { add(j+n,i,inf); } } } ll ans1=dinic(); for(int i=1;i<=n;i++) { int x=p[i]; S=x;T=x+n; if(f[x*2]||tell())continue; S=x;T=0;dinic(); S=2*n+1;T=x+n;dinic(); ss.push_back(x); f[x*2]=f[x*2+1]=0; } sort(ss.begin(),ss.end()); printf("%lld %d\n",ans1,ss.size()); for(int i=0;i<ss.size();i++) { printf("%d%c",ss[i]," \n"[i==ss.size()-1]); } } return 0;}
3532: [Sdoi2014]Lis 最小字典序最小割
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。