「SDOI2014」LIS - LIS+拆点+最小割

题目大意

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

---

题目分析

先求出LIS，将可能的LIS转移路径用建成网络流图。
即，每个点拆成入点和出点，入出点连边$B_i$表示割掉的代价。
按照LIS转移路径从出点到入点连边，$f_i=1$的从$S$连边，$f_i=Max_f$的向$T$连边。
最大流就是第一问答案。
到这里都很显然。

第二问可以按照$C_i$从小到大的顺序依次删边验证最大流是否变小来确定割集，但会TLE。
考虑，删去$u\rightarrow v$最大流是否会变小即当前残余网络是否还能从$u\rightarrow v$，若不能，删去后一定会变小，加入割集。

为了排除其他割集的影响，若确定一条边在割集内，需要将其从残余网络中删除，并用网络流更新残余网络。
然而，这样依然会TLE。
考虑退流算法，在残余网络中从$T$到$v$跑一次最大流，从$u$到$S$跑一次最大流，即可删除影响。
正确性在于因为$u$不能到达$v$，因此$u$不能到达$T$，而$v$显然也不能到达$T$，故不会对其他路径产生影响。

然后就可以卡常了，发现我的dinic竟然还可以优化，已加入代码库。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=1405;

struct Edge {
	int from,to,cap,flow;
	Edge(int x=0,int y=0,int c=0,int f=0):from(x),to(y),cap(c),flow(f) {}
};

struct Dinic {
	int n,m,s,t;
	vector<Edge>edges;
	vector<int>G[maxn];
	bool vst[maxn];
	int dist[maxn],cur[maxn];
	void init(int n) {
		this->n=n;
		edges.clear();
		for(int i=1; i<=n; i++)G[i].clear();
	}
	void AddEdge(int x,int y,int v) {
		edges.push_back(Edge(x,y,v,0));
		edges.push_back(Edge(y,x,0,0));
		m=edges.size();
		G[x].push_back(m-2);
		G[y].push_back(m-1);
	}
	bool bfs() {
		for(int i=1; i<=n; i++)vst[i]=0;
		queue<int>Q;
		Q.push(t); //reversed
		vst[t]=1;
		while(!Q.empty()) {
			int Now=Q.front();
			Q.pop();
			for(int id:G[Now]) {
				Edge& e=edges[id^1];
				int Next=e.from;
				if(!vst[Next]&&e.cap>e.flow) { 
					vst[Next]=1;
					dist[Next]=dist[Now]+1;
					if(Next==s)return 1;
					Q.push(Next);
				}
			}
		}
		return vst[s];
	}
	int dfs(int Now,int a) {
		if(Now==t||a==0)return a;
		int flow=0;
		for(int& i=cur[Now]; i<G[Now].size(); i++) {
			Edge& e=edges[G[Now][i]];
			int Next=e.to;
			if(dist[Now]-1!=dist[Next])continue;
			int nextflow=dfs(Next,min(a,e.cap-e.flow));
			if(nextflow>0) {
				e.flow+=nextflow;
				edges[G[Now][i]^1].flow-=nextflow;
				flow+=nextflow;
				a-=nextflow;
				if(a==0)break;
			}
		}
		return flow;
	}
	int maxflow(int s,int t) {
		this->s=s;
		this->t=t;
		int flow=0;
		while(bfs()) {
			memset(cur,0,sizeof(cur));
			flow+=dfs(s,INT_MAX);
		}
		return flow;
	}
} dinic;

struct node {
	int v,id;
	bool operator < (const node& b) const {
		return v<b.v;
	}
} c[maxn];

int n,a[maxn],b[maxn],f[maxn],Max=0;
vector<int> ans;

int main() {
	int t=Get_Int();
	while(t--) {
		n=Get_Int();
		for(int i=1; i<=n; i++)a[i]=Get_Int();
		for(int i=1; i<=n; i++)b[i]=Get_Int();
		for(int i=1; i<=n; i++)c[i].v=Get_Int(),c[i].id=i;
		Max=0;
		for(int i=1; i<=n; i++) {
			f[i]=1;
			for(int j=1; j<i; j++)if(a[j]<a[i])f[i]=max(f[i],f[j]+1);
			Max=max(Max,f[i]);
		}
		int S=n*2+1,T=n*2+2;
		dinic.init(T);
		for(int i=1; i<=n; i++)dinic.AddEdge(i,n+i,b[i]);
		for(int i=1; i<=n; i++)if(f[i]==1)dinic.AddEdge(S,i,INT_MAX/2);
		for(int i=1; i<=n; i++)if(f[i]==Max)dinic.AddEdge(n+i,T,INT_MAX/2);
		for(int i=1; i<=n; i++)
			for(int j=1; j<i; j++)
				if(a[j]<a[i]&&f[i]==f[j]+1)dinic.AddEdge(n+j,i,INT_MAX/2);
		int ans1=dinic.maxflow(S,T);
		sort(c+1,c+n+1);
		ans.clear();
		for(int i=1; i<=n; i++) {
			int u=c[i].id,v=n+c[i].id;
			dinic.s=u,dinic.t=v;
			if(dinic.bfs())continue;
			dinic.maxflow(T,v),dinic.maxflow(u,S);
			ans.push_back(c[i].id);
		}
		sort(ans.begin(),ans.end());
		printf("%d %d\n",ans1,ans.size());
		for(int x:ans)printf("%d ",x);
		putchar('\n');
	}
	return 0;
}