【网络流24题】最长不下降子序列问题

标签：网络流/最大流

Solution

Part 1

直接 dp 求解。

Part 2

设最长 LIS 长度为 \(Ans\)。

因为每个数只能使用一次，考虑拆成两个点 \(X_i\) 与 \(Y_i\)，分别表示入点与出点，其中使 \(X_i\) 向 \(Y_i\) 连一条容量为 \(1\) 的边，表示这个数只能使用一次。

对于 \(i\)，使 \(Y_i\) 向所有满足 \(j 并且 \(dp[j]=dp[i]-1\)， \(A[j] \leq A[i]\) 的 \(X_j\) 连边。

若 \(dp[i] = Ans\)，则从源点 \(S\) 向 \(X_i\) 连一条容量为 \(1\) 的边。若 \(dp[i] = 1\)，则从 \(Y_i\) 向汇点 \(T\) 连一条容量为 \(1\) 的边。

跑一边最大流，得到的最大流量即为答案。

Part 3

对于 \(Ans=1\) 的情况特判，以下讨论 \(Ans >= 2\) 的情况。

在 Part 2 的基础上，将 \(< Y_1 , X_1 >\) 与 \(< Y_n , X_n >\) 的容量改为 \(inf\) ，表示可以无限取。

若存在 \(< S , X_n >\) ，\(< Y_1 , T >\) 这种边，也将他们的容量改为 \(inf\) ，因为它们都可以给出无限次贡献。

另外的，若 \(Ans = 2\) 且存在 \(< Y_n , X_1 >\) ，则将其删去，否则会造成贡献计算无限次的情况，最后再将其贡献加上。

跑一边最大流，得到的最大流量即为答案。

Code

#include
#define N 1205
#define M 30005
using namespace std;
typedef long long ll;
typedef double db;
char IO;
int rd(){
	int num=0;bool f=0;
	while(IO=getchar(),IO<48||IO>57)if(IO=='-')f=1;
	do num=(num<<1)+(num<<3)+(IO^48);
	while(IO=getchar(),IO>=48&&IO<=57);
	return f?-num:num;
}
bool f2;
int n,S,T;
int to[M],nxt[M],hd[N],val[M],cnte=1;
void Adde(int u,int v,int w){
	to[++cnte]=v;val[cnte]=w;
	nxt[cnte]=hd[u];hd[u]=cnte;
}
void Add(int u,int v,int w){
	Adde(u,v,w);Adde(v,u,0);
}
int dep[M],cur[M];
queue Q;
int BFS(){
	memset(dep,0,sizeof(dep));
	memcpy(cur,hd,sizeof(cur));
	dep[S]=1;Q.push(S);
	int u,v;
	while(!Q.empty()){
		u=Q.front();Q.pop();
		for(int i=hd[u];i;i=nxt[i]){
			if(val[i]&&!dep[v=to[i]]){
				dep[v]=dep[u]+1;
				Q.push(v);
			}
		}
	}
	return dep[T];
}
int DFS(int u,int flow){
	if(u==T)return flow;
	int res=0,f,v;
	for(int i=cur[u];i&&flow;i=nxt[i]){
		cur[u]=i;v=to[i];
		if(dep[v]!=dep[u]+1)continue;
		if(val[i]&&(f=DFS(v,min(flow,val[i])))>0){
			val[i]-=f;val[i^1]+=f;
			flow-=f;res+=f;
		}
	}return res;
}
int A[N],dp[N];
bool f1;
int main(){
//	cout<<1.0*(&f1-&f2)/1024.0/1024.0<

相关

标签