关于CE
  • 板块灌水区
  • 楼主Effulgent
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/2/14 14:50
  • 上次更新2023/11/5 03:17:18
查看原帖
关于CE
40078
Effulgent楼主2021/2/14 14:50

如下程序为什么会CE。

本地编译都过了

原来没有CE的程序交上去现在也会CE。。。。。

#include<bits/stdc++.h>
#define N 500010
using namespace std;
int h[N],nxt[N],v[N],w[N],s,t,dep[N/5],ec,n,a[N/5],b[N/5],c[N/5],d[N/5],v1[N/5],v2[N/5],v3[N/5],ct,v4[N/5];
int tx[]={1,-1,0,0,0,0},ty[]={0,0,1,-1,0,0},tz[]={0,0,0,0,1,-1};
struct no{
	int x,y,z;
};
int operator <(no x,no y){
	return x.x<y.x||(x.x==y.x&&(x.y<y.y||(x.y==y.y&&(x.z<y.z))));
}
map<no,vector<int> >ma;
vector<int>g[3]; 
void add(int a,int b,int c){v[++ec]=b;w[ec]=c;nxt[ec]=h[a];h[a]=ec;}
void adj(int a,int b,int c){add(a,b,c);add(b,a,0);}
bool bfs(){
    queue<int>q;
	q.push(s);
	for(int i=0;i<=ct+4;i++)
		dep[i]=0;
	dep[s]=1;
    while(!q.empty()){
        int x=q.front();
		q.pop();
        for(int i=h[x];i;i=nxt[i])
            if(w[i]&&!dep[v[i]]){
            	dep[v[i]]=dep[x]+1;
				q.push(v[i]);
			}
    }
	return dep[t];
}
int dfs(int x,int dis){
    if(x==t)
		return dis;
	int tp=dis;
    for(int i=h[x];i;i=nxt[i])
        if(dep[v[i]]==dep[x]+1&&w[i]){
            int f=dfs(v[i],min(tp,w[i]));
            if(!f)
            	dep[v[i]]=0;
            tp-=f;
            w[i]-=f;
			w[i^1]+=f;
			if(!tp)
				break;
        }
	return dis-tp;
}
int din(){
    int aans=0;
    while(bfs())
		aans+=dfs(s,1e9);
    return aans;
}
int main(){
	ec=1;
	int ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
		no va=(no){a[i],b[i],c[i]};
		if((a[i]+b[i]+c[i]+300000)%3==0)
			d[i]*=11;
		else
			d[i]*=10;
		ans+=d[i];
		ma[va].push_back(i);
		g[(a[i]+b[i]+c[i]+300000)%3].push_back(i);
	}
	for(int i=0;i<g[1].size();i++){
		int x=g[1][i];
		v1[x]=++ct;
	}
	for(int i=0;i<g[0].size();i++){
		int x=g[0][i];
		v2[x]=++ct;
		v3[x]=++ct;
		adj(v2[x],v3[x],d[x]);
	}
	for(int i=0;i<g[2].size();i++){
		int x=g[2][i];
		v4[x]=++ct;
	}
	s=0;
	t=ct+1;
	for(int i=1;i<=n;i++)
		if(v1[i])
			adj(s,v1[i],d[i]);
	for(int i=1;i<=n;i++)
		if(v4[i])
			adj(v4[i],t,d[i]);
	for(int i=1;i<=n;i++)
		if(v1[i]){
			for(int j=0;j<6;j++){
				int ax=a[i]+tx[j],ay=b[i]+ty[j],az=c[i]+tz[j];
				no va=(no){ax,ay,az};
				vector<int>v=ma[va];
				for(int k=0;k<v.size();k++){
					int x=v[k];
					if(v2[x])
						adj(v1[i],v2[x],1e9);
				}
			}
		}
	for(int i=1;i<=n;i++)
		if(v3[i]){
			for(int j=0;j<6;j++){
				int ax=a[i]+tx[j],ay=b[i]+ty[j],az=c[i]+tz[j];
				no va=(no){ax,ay,az};
				vector<int>v=ma[va];
				for(int k=0;k<v.size();k++){
					int x=v[k];
					if(v4[x])
						adj(v3[i],v4[x],1e9);
				}
			}
		}
	printf("%.1f",(ans-din())*(0.1));
}
2021/2/14 14:50
加载中...