关于常数的一点小问题
  • 板块学术版
  • 楼主剑雪清寒
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/9/16 19:45
  • 上次更新2023/10/27 11:25:07
查看原帖
关于常数的一点小问题
214728
剑雪清寒楼主2022/9/16 19:45

[AHOI2009]最小割中,我的代码以如下方式存图与跑网络流,获得了92ms的成绩

//存图
struct gra {
	edge rd[60000],*head[4001];int rs;
	inline void add(int u,int v,int lim) {
		rd[rs].self=u;rd[rs].to=v;rd[rs].name=rs;rd[rs].lim=lim;rd[rs].next=head[u];head[u]=&rd[rs++];
	}
}g1,g2;
//跑图(网络流部分截取)
for(edge *i=g1.head[x];i;i=i->next) {
		int nex=i->to;
		if(i->lim && dist[nex]+1==dist[x]) {
			int cost=ISAP(nex,std::min(i->lim,lim-used));
			if(cost) {
				i->lim-=cost;
				g2.rd[i->name].lim+=cost;
				used+=cost;
				if(used==lim) return used;
			}
		}
	}
	for(edge *i=g2.head[x];i;i=i->next) {
		int nex=i->to;
		if(i->lim && dist[nex]+1==dist[x]) {
			int cost=ISAP(nex,std::min(i->lim,lim-used));
			if(cost) {
				i->lim-=cost;
				g1.rd[i->name].lim+=cost;
				used+=cost;
				if(used==lim) return used;
			}
		}
	}

而以如下方式,则是1.26s的好成绩

//含义同上
struct gra {
	edge rd[120000],*head[4001];int rs;
	inline void add(int u,int v,int lim) {
		rd[rs].self=u;rd[rs].to=v;rd[rs].name=rs;rd[rs].lim=lim;rd[rs].next=head[u];head[u]=&rd[rs++];
		rd[rs].self=v;rd[rs].to=u;rd[rs].name=rs;rd[rs].lim=0;rd[rs].next=head[v];head[v]=&rd[rs++];
	}
}g1,g2;
//
for(edge *i=g1.head[x];i;i=i->next) {
		int nex=i->to;
		if(i->lim && dist[nex]+1==dist[x]) {
			int cost=ISAP(nex,std::min(i->lim,lim-used));
			if(cost) {
				i->lim-=cost;
				g1.rd[i->name^1].lim+=cost;
				used+=cost;
				if(used==lim) return used;
			}
		}
	}
2022/9/16 19:45
加载中...