响应式网站下载,合肥seo网站建设费用,西安谷歌推广,网站制作与网页设计课程设计来自FallDeram的博客#xff0c;未经允许#xff0c;请勿转载#xff0c;谢谢。 给定序列A#xff0c;序列中的每一项Ai有删除代价Bi和附加属性Ci。请删除若项#xff0c;使得4的最长上升子序列长度减少至少1#xff0c;且付出的代价之和最小#xff0c;并输出方案。如果…来自FallDeram的博客未经允许请勿转载谢谢。 给定序列A序列中的每一项Ai有删除代价Bi和附加属性Ci。请删除若项使得4的最长上升子序列长度减少至少1且付出的代价之和最小并输出方案。如果有多种方案请输出将删去项的附加属性排序之后字典序最小的一种。 T5 n700 首先考虑建图之后最小割 每个点拆成两个点中间连费用的边 f[i]表示以i为开头的最长上升子序列长度对于ija[i]a[j]f[i]f[j]1 从i的出点向j的入点连INF的边 然后随意求一个最小割按照优先级从小到大考虑每个点。 一条边可以被割当且仅当这条边连接了两个不同的强联通块。 所以只要一条边能被割就把它加入答案然后把u-S,T-v的流量全部退掉即可。 #includealgorithm
#includeiostream
#includecstring
#includecstdio
#includevector
#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[T5],c[T5],q[T5],d[T5],n,mx,cnt1,F,a[T5],b[T5],top,rk[T5],C[T5],f[T5];
vectorint 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[topi1]From]1;itop;i)for(int jc[q[i]]head[q[i]];j;je[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(xTo) return f;int used0;for(intic[x];i;ie[i].next)if(e[i].wd[e[i].to]d[x]1){int wdfs(e[i].to,To,min(f-used,e[i].w));usedw;e[i].w-w;e[i^1].ww;if(usedf) return f;}return d[x]-1,used;
}
bool cmp(int x,int y){return C[x]C[y];}
int main()
{for(int casread();cas;--cas){nread();cntmx1;ans.clear();memset(head,0,sizeof(head));for(int i1;in;i) a[i]read(),rk[i]i;for(int i1;in;i) ins(i,in,read());for(int i1;in;i) C[i]read();for(int in;i;--i){f[i]1;for(int ji1;jn;j) if(a[j]a[i])f[i]max(f[i],f[j]1);mxmax(mx,f[i]);}for(int i1;in;i){if(f[i]mx) ins(S,i,INF);if(f[i]1) ins(in,T,INF);for(int ji1;jn;j)if(a[j]a[i]f[j]f[i]-1)ins(in,j,INF); }F0;while(bfs(S,T)) Fdfs(S,T,INF);sort(rk1,rkn1,cmp);for(int i1;in;i){int xrk[i];if(e[x1].w||bfs(x,xn)) continue; e[x1].we[x1|1].w0;while(bfs(x,S)) dfs(x,S,INF);while(bfs(T,xn)) dfs(T,xn,INF);ans.push_back(x);} printf(%d %d\n,F,ans.size());sort(ans.begin(),ans.end());for(int i0;ians.size();i)printf(%d%c,ans[i],(i1ans.size())?\n: );}return 0;
} 转载于:https://www.cnblogs.com/FallDream/p/bzoj3532.html
