在[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;
}
}
}