来自FallDeram的博客，未经允许，请勿转载，谢谢。

---

 

给定序列A，序列中的每一项Ai有删除代价Bi和附加属性Ci。请删除若项，使得4的最长上升子序列长度减少至少1，且付出的代价之和最小，并输出方案。如果有多种方案，请输出将删去项的附加属性排序之后，字典序最小的一种。

T<=5 n<=700

 

首先考虑建图之后最小割  每个点拆成两个点中间连费用的边

f[i]表示以i为开头的最长上升子序列长度，对于i<j&&a[i]<a[j]&&f[i]==f[j]+1 从i的出点向j的入点连INF的边

然后随意求一个最小割，按照优先级从小到大考虑每个点。

一条边可以被割，当且仅当这条边连接了两个不同的强联通块。

所以只要一条边能被割，就把它加入答案，然后把u->S,T->v的流量全部退掉即可。

#include
     
      #include
      
       #include
       
         #include
        
         #include
         
          #define S 0#define T 1401#define INF 2000000000 using namespace std;inline int read(){    int x = 0 , f = 1; char ch = getchar();    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;}struct edge{
   int to,next,w;}e[T*100];int head[T+5],c[T+5],q[T+5],d[T+5],n,mx,cnt=1,F,a[T+5],b[T+5],top,rk[T+5],C[T+5],f[T+5];vector
          
            ans;inline void ins(int f,int t,int w){ e[++cnt]=(edge){t,head[f],w};head[f]=cnt; e[++cnt]=(edge){f,head[t],0};head[t]=cnt; }bool bfs(int From,int To){ memset(d,0,sizeof(d));int i,j; for(d[q[top=i=1]=From]=1;i<=top;++i) for(int j=c[q[i]]=head[q[i]];j;j=e[j].next) if(e[j].w&&!d[e[j].to]) d[q[++top]=e[j].to]=d[q[i]]+1; return d[To]; }int dfs(int x,int To,int f){ if(x==To) return f;int used=0; for(int&i=c[x];i;i=e[i].next) if(e[i].w&&d[e[i].to]==d[x]+1) { int w=dfs(e[i].to,To,min(f-used,e[i].w)); used+=w;e[i].w-=w;e[i^1].w+=w; if(used==f) return f; } return d[x]=-1,used;}bool cmp(int x,int y){ return C[x]
           
            a[i]) f[i]=max(f[i],f[j]+1); mx=max(mx,f[i]); } for(int i=1;i<=n;++i) { if(f[i]==mx) ins(S,i,INF); if(f[i]==1) ins(i+n,T,INF); for(int j=i+1;j<=n;++j) if(a[j]>a[i]&&f[j]==f[i]-1) ins(i+n,j,INF); } F=0;while(bfs(S,T)) F+=dfs(S,T,INF); sort(rk+1,rk+n+1,cmp); for(int i=1;i<=n;++i) { int x=rk[i]; if(e[x<<1].w||bfs(x,x+n)) continue; e[x<<1].w=e[x<<1|1].w=0; while(bfs(x,S)) dfs(x,S,INF); while(bfs(T,x+n)) dfs(T,x+n,INF); ans.push_back(x); } printf("%d %d\n",F,ans.size()); sort(ans.begin(),ans.end()); for(int i=0;i