数据下载有误
查看原帖
数据下载有误
297355
InsomniaFly楼主2022/12/2 11:46

帮朋友发的,#11 和 #13 挂了

然而下载数据调的时候 #11 成了锟斤拷

怎么会是呢

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=880;
const int M=640000;
const int INF=1e11;
int a[880];
int f[880];
int S,T;
int head[N],idx;
void clear(){
	memset(head,-1,sizeof(head));
	idx=0;
}
struct Node{
	int ne;
	int ve;
	int f;
}edge[2*M];
void added(int x,int y,int f){
	edge[idx].ne=head[x];
	edge[idx].ve=y;
	edge[idx].f=f;
	head[x]=idx;
	idx++;
	edge[idx].ne=head[y];
	edge[idx].ve=x;
	edge[idx].f=0;
	head[y]=idx;
	idx++;
}
int d[N];
int q[N];
int cur[N];
bool bfs(){
	int hh=0;
	int tt=0;
	memset(d,-1,sizeof(d));
	q[0]=S;
	d[S]=1;
	cur[S]=head[S];
	while(hh<=tt){
		int t=q[hh++];
		for(int i=head[t];i!=-1;i=edge[i].ne){
			int ver=edge[i].ve;
			if(d[ver]==-1&&edge[i].f){
				d[ver]=d[t]+1;
				cur[ver]=head[ver];
				if(ver==T){
					return true;	
				}
				q[++tt]=ver;
			}
		}
	}
	return false;
}
int find(int u,int limit){
	if(u==T){
		return limit;
	}
	else{
		int flow=0;
		for(int i=cur[u];i!=-1&&flow<limit;i=edge[i].ne){
			int ver=edge[i].ve;
			if(d[ver]==d[u]+1&&edge[i].f){
				int t=find(ver,min(limit-flow,edge[i].f));
				if(!t) d[ver]=-1;
				else{
					edge[i].f-=t;
					edge[i^1].f+=t;
					flow+=t;
				}
			}
		}
		return flow;
	}
}
int dinic(){
	int r=0;
	int flow;
	while(bfs()){
		while(flow=find(S,INF)){
			r+=flow;
		}
	}
	return r;
}
signed main(){
	int n;
	clear();
	cin>>n;
	S=0;
	T=2*n+10;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		added(i,i+n,1);
		f[i]=1;
	}
	int s=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[i]>=a[j]){
				f[i]=max(f[i],f[j]+1);
				s=max(s,f[i]);
			}
		}
		for(int j=1;j<i;j++){
			if(f[i]==f[j]+1&&a[i]>=a[j]) added(j+n,i,1);
		}
		if(f[i]==1) added(S,i,1);
	}
	for(int i=1;i<=n;i++){
		if(f[i]==s) added(i+n,T,1);
	}
	if(s==1){
		cout<<s<<endl<<n<<endl<<n<<endl;
		return 0;
	} 
	else{
		cout<<s<<endl;
		int res=dinic();
		cout<<res<<endl;
		added(S,1,INF);
		added(1,1+n,INF);
		added(n,2*n,INF);
		if(f[n]==s){
			added(2*n,T,INF);
		}
		cout<<res+dinic();
	}
	return 0;
} 
2022/12/2 11:46
加载中...