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

1
6
3 4 4 2 2 3
2 1 1 1 1 2
6 5 4 3 2 1

Sample Output

4 3
2 3 6
解釋：刪去(A2，43，A6)，(A1，A6)，(A2，43，44，A5)等都是合法的方案，但
{A2，43，A6)對應的C值的字典序最小。

HINT

?

1 < =N < =700???? T < =5

/*如果沒有字典序最小的要求，建圖跑最小割。建圖方法：S向i連一條容量為inf的邊；i'向T連一條容量為inf的邊；i向i'連一條容量為b[i]的邊；如果a[i]<a[j]&&f[i]+1=f[j]，i'向j連一條容量為inf的邊。現在有字典序最小的要求，那么有字典序從小到大枚舉刪哪條邊，刪一條邊<u,v>的方法是：退流，u向S跑一遍最大流，，T向v跑一遍最大流，然后這條邊流量清零就行了。 */ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #define N 710 #define inf 1000000000 using namespace std; int a[N],b[N],f[N],head[N],dis[N],n,cnt,ans[N]; struct Node{int num,id;}c[N]; struct node{int v,f,pre;}e[N*N]; queue<int> q; bool cmp(const Node&x,const Node&y){return x.num<y.num;} void add(int u,int v,int f){e[++cnt].v=v;e[cnt].f=f;e[cnt].pre=head[u];head[u]=cnt;e[++cnt].v=u;e[cnt].f=0;e[cnt].pre=head[v];head[v]=cnt; } bool bfs(int S,int T){memset(dis,-1,sizeof(dis));q.push(S);dis[S]=0;while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i;i=e[i].pre)if(e[i].f&&dis[e[i].v]==-1){dis[e[i].v]=dis[u]+1;q.push(e[i].v);}}return dis[T]!=-1; } int dfs(int x,int f,int T){if(x==T||f==0) return f;int rest=f;for(int i=head[x];i;i=e[i].pre)if(e[i].f&&dis[e[i].v]==dis[x]+1){int v=dfs(e[i].v,min(rest,e[i].f),T);if(!v) dis[e[i].v]=-1;e[i].f-=v;e[i^1].f+=v;rest-=v;}if(f==rest) dis[x]=0;return f-rest; } int dinic(int S,int T){int ans=0;while(bfs(S,T)) ans+=dfs(S,inf,T);return ans; } int DP(){int maxf=0;for(int i=1;i<=n;i++){int maxn=0;for(int j=0;j<i;j++)if(a[j]<a[i]) maxn=max(maxn,f[j]);f[i]=maxn+1;maxf=max(maxf,f[i]);}return maxf; } void build(int S,int T){int maxf=DP();for(int i=1;i<=n;i++) add(i,i+n,b[i]);for(int i=1;i<=n;i++){if(f[i]==1) add(S,i,inf);else if(f[i]==maxf) add(i+n,T,inf);for(int j=i+1;j<=n;j++)if(a[i]<a[j]&&f[i]+1==f[j])add(i+n,j,inf);} } int main(){int Q;scanf("%d",&Q);while(Q--){memset(head,0,sizeof(head));cnt=1;scanf("%d",&n);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].num),c[i].id=i;int S=0,T=n*2+1;build(S,T);int maxflow=dinic(S,T);sort(c+1,c+n+1,cmp);int tot=0;for(int i=1;i<=n;i++){int u=c[i].id,v=u+n;if(bfs(u,v)) continue;ans[++tot]=u;dinic(u,S);dinic(T,v);e[u*2].f=e[u*2+1].f=0;}sort(ans+1,ans+tot+1);printf("%d %d\n",maxflow,tot);for(int i=1;i<=tot;i++)printf("%d%c",ans[i],i==tot?'\n':' ');}return 0; }

?

轉載于:https://www.cnblogs.com/harden/p/6720315.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的Lis（bzoj 3532）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。