P2766 最长不下降子序列问题题解（网络流）

题目链接

解题思路

分成三小问解决。

第一小问，求\(LIS\)，因为\(n<=500\)，直接\(O(N^2)\)暴力求解即可。

第二三小问，建立模型用网络流求解。

对于第二小问

\((1)\)首先，因为每个点只能使用一次，考虑拆点，把每一个点拆成\(i，n+i\)两个点，从\(i\)连向\(n+i\)一条长度为\(1\)的有向边。

\((2)\)其次，因为流向是从S经集合E到T，其中任意集合E中元素\(i\)需要满足的条件是\(i\)位于LIS上，故：

①出边从\(lis[i]=k\)的点流向T

②所有的能构成E的边都需要加入，也就是任意\(i,j\)满足\(i<j，a[i]<a[j]，lis[i]=lis[j]-1\)都从\(i\)到\(j\)连边。

跑一遍最大流即可。

第三小问唯一的不同就是\(S\)流向\(1\)，\(1\)流向\(1+n\)，\(n\)流向\(n+n\)，\(n+n\)流向\(T\)四条路长度变成\(inf\)而已，改后再跑一遍最大流即可。

AC代码

#include<stdio.h>

#include<string.h>

int lis[1020],a[1020],len;//lis

int s,t,inf=0x3fffffff;//ek

struct Edge{

	int end,length,near;

}edge[50020];

int head[1020],cnt=2,vis[1020];

void addedge(int begin,int end,int length){

	edge[cnt].end=end;

	edge[cnt].length=length;

	edge[cnt].near=head[begin];

	head[begin]=cnt;

	cnt++;

}

struct Pre{

	int pre,ednum;

}pre[1020];

int bfs(){

	memset(vis,0,sizeof(vis));

	int queue[50010]={0},headq=0,tail=0,i;

	queue[tail++]=s;

	vis[s]=1;

	while(headq<tail){

		int v=queue[headq];

		for(i=head[v];i;i=edge[i].near){

			int p=edge[i].end;

			if(vis[p]||!edge[i].length)continue;

			vis[p]=1;

			pre[p].pre=v;

			pre[p].ednum=i;

			queue[tail++]=p;

			if(p==t)return 1;

		}

		headq++;

	}

	return 0;

}

int ek(){

	int min,ans=0,i;

	while(bfs()){

		min=inf;

		for(i=t;i!=s;i=pre[i].pre){

			int en=pre[i].ednum;

			if(min>edge[en].length)min=edge[en].length;

		}

		for(i=t;i!=s;i=pre[i].pre){

			int en=pre[i].ednum;

			edge[en].length-=min;

			edge[en^1].length+=min;

		}

		ans+=min;

	}

	return ans;

}

int main(){

	int i,j,n;

	scanf("%d",&n);

	s=2*n+3;

	t=2*n+4;

	for(i=1;i<=n;i++){

		scanf("%d",&a[i]);

		lis[i]=1;

	}

	//lis n<=500 O(N2)

	for(i=1;i<=n;i++)

		for(j=1;j<i;j++)

			if(a[i]>=a[j]&&lis[i]<lis[j]+1)lis[i]=lis[j]+1;

	for(i=1;i<=n;i++)if(lis[i]>len)len=lis[i];

	printf("%d\n",len);

	//ek1 建图求最大流

	for(i=1;i<=n;i++){

		addedge(i,i+n,1);//拆点

		addedge(i+n,i,0);

		if(lis[i]==1){

			addedge(s,i,1);

			addedge(i,s,0);

		}

		if(lis[i]==len){

			addedge(i+n,t,1);

			addedge(t,i+n,0);

		}

	}

	for(i=1;i<=n;i++){

		for(j=1;j<i;j++){

			if(lis[i]==lis[j]+1&&a[i]>=a[j]){

				addedge(j+n,i,1);	addedge(i,j+n,0);

			}

		}

	}

	printf("%d\n",ek());

	//ek2

	memset(pre,0,sizeof(pre));

	memset(edge,0,sizeof(edge));

	memset(head,0,sizeof(head));

	cnt=2;

	for(i=1;i<=n;i++){

		addedge(i,i+n,1);//拆点

		addedge(i+n,i,0);

		if(lis[i]==1){

			addedge(s,i,1);

			addedge(i,s,0);

		}

		if(lis[i]==len){

			addedge(i+n,t,1);

			addedge(t,i+n,0);

		}

	}

	for(i=1;i<=n;i++){

		for(j=1;j<i;j++){

			if(lis[i]==lis[j]+1&&a[i]>=a[j]){

				addedge(j+n,i,1);	addedge(i,j+n,0);

			}

		}

	}

	addedge(1,1+n,inf);	addedge(1+n,1,0);

	addedge(s,1,inf); 	addedge(1,s,0);

	if(lis[n]==len){

		addedge(n,n+n,inf);		addedge(n+n,n,0);

		addedge(n+n,t,inf);		addedge(t,n+n,0);

	}

	printf("%d\n",ek());

	return 0;

}

巴特西

P2766 最长不下降子序列问题题解（网络流）

题目链接

解题思路

AC代码

最新文章

热门文章

巴特西

P2766 最长不下降子序列问题 题解（网络流）

题目链接

解题思路

AC代码

最新文章

热门文章

P2766 最长不下降子序列问题题解（网络流）