92分求助
查看原帖
92分求助
315205
Kniqht楼主2023/12/16 18:09

就WA了一个点,有没有大佬也有同样错误啊?

这两天有难度的题都调不出来,真破防了

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,M=1e6+10,inf=0x3f3f3f3f;
int n,m,s,t;
int h[M],e[M*2],ne[M*2],w[M*2],idx,l[210][210];
void add(int a,int b,int c){
	e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
	e[idx]=a,ne[idx]=h[b],w[idx]=0,h[b]=idx++;
}
int a[N];
int cur[N],d[N];
bool bfs(){
	for(int i=1;i<=2*n+1;i++) d[i]=inf;
	queue<int> q;
	q.push(s);
	d[s]=0;
	cur[s]=h[s];
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=h[x];~i;i=ne[i]){
			int j=e[i];
			if(w[i]>0&&d[j]==inf){
				q.push(j);
				cur[j]=h[j];
				d[j]=d[x]+1;
				if(j==t) return 1;
			}
		}
	}
	return 0;
}
int dinic(int x,int flow){
	if(x==t) return flow;
	int res=0,k;
	for(int i=cur[x];~i&&flow;i=ne[i]){
		cur[x]=i;
		int j=e[i]; 
		if(w[i]>0&&d[j]==d[x]+1){
			k=dinic(j,min(flow,w[i]));
			if(!k) d[j]=inf;
			w[i]-=k;
			w[i^1]+=k;
			res+=k; 
			flow-=k;
		}
	}
	return res;
} 
int maxflow(){
	int flow=0;
	while(bfs()) flow+=dinic(s,inf);
	return flow; 
}
int f[N];
signed main(){
	memset(h,-1,sizeof(h));
	scanf("%lld",&n);
	s=0,t=2*n+1;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),f[i]=1;
	int len=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++)
			if(a[j]<=a[i]) f[i]=max(f[i],f[j]+1);
		len=max(len,f[i]);
	}
	printf("%lld\n",len);
	for(int i=1;i<=n;i++) add(i,i+n,1);
	for(int i=1;i<=n;i++){
		if(f[i]==1) add(s,i,1);
		if(f[i]==len) add(i+n,t,1);
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<i;j++)
			if(a[j]<=a[i]&&f[i]==f[j]+1) add(j+n,i,1);
	int ans;
	printf("%lld\n",ans=maxflow());
	add(1,1+n,inf);add(s,1,inf);
	if(f[n]==len) add(n+n,t,inf),add(n,n+n,inf);
	printf("%lld",ans+maxflow());
	return 0;
}
2023/12/16 18:09
加载中...