SAP模板 - #include <Seter> - using namespace Orz;

SAP模板

Seter posted @ 2011年8月22日 20:00 in Practice with tags NetworkFlow , 1955 阅读

自己写的SAP,很短,35行,很快,测试了一些题速度都能排到前十左右。

优化:

1.不要用递归……递归好写但是慢到暴……而且也不是很短……

2.当前弧优化。保存每个点当前沿着哪条弧增广,在下次增广时直接从这条弧开始。

3.断层优化(这个我觉得不是很显然但是总之是对的)。比如有dis为1,2,3,5,6的点唯独没有dis为4的点,此时就可以证明不可能再增广了。具体操作是用gap[i]表示dis为i的点数,某个dis改变时如果gap[dis]=1(即dis改变后gap[dis]=0)的话就结束。

4.多弧增广。找到增广路后不退回s而是退回瓶颈前的那个点。

5.不用BFS预处理。复杂度一样,预处理增加代码复杂度和代码长度只快了那么一点点时间。而且测试出来BFS预处理后断层优化会萎(我承认这个一定是我写次了)。

#include <stdio.h>
#include <Seter>
#define maxn 200
#define maxm 200
inline getint(){
	int re=0,ch=getchar();
	while(ch<'0'||ch>'9')if((ch=getchar())<=0)return -1;
	for(;ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return re;
}int dis[maxn],gap[maxm+1],m=0,flow=0,n,i,d,s=0,t;
struct edge{int x,t,y;struct edge *opp,*next;}*map[maxn],*neck[maxn],*from[maxn],*cur[maxn],st[maxm<<1],*p;
inline void ADDEDGE(x,y,t){
	st[m].next=map[st[m^1].y=st[m].x=x];st[m^1].next=map[st[m].y=st[m^1].x=y];
	(st[m^1].opp=map[x]=st+m)->t=t;st[m].opp=map[y]=st+(m^1);m+=2;
}main(){
	int x,y,z;
	for(i=getint(),t=(gap[0]=getint())-1;i;i--){
		x=getint();y=getint();z=getint();
		ADDEDGE(x-1,y-1,z);
	}for(i=s,m>>=1;dis[s]<=m;){
		for(cur[i]||(cur[i]=map[i]);cur[i];cur[i]=cur[i]->next)if(cur[i]->t&&dis[cur[i]->y]+1==dis[i]){
			neck[(from[cur[i]->y]=cur[i])->y]=s==i?cur[i]:neck[i]->t>cur[i]->t?cur[i]:neck[i];
			if((i=cur[i]->y)==t){
				for(flow+=d=neck[t]->t;i!=s;i=from[i]->x)from[i]->t-=d,from[i]->opp->t+=d;
				i=neck[t]->x;
			}break;
		}if(!cur[i]){
			if(!--gap[dis[i]])break;
			for(dis[i]=m,p=map[i];p;p=p->next)if(p->t&&dis[p->y]<dis[i])dis[i]=dis[(cur[i]=p)->y];
			gap[++dis[i]]++;
			i=i==s?s:from[i]->x;
		}
	}printf("%d\n",flow);
	return 0;
}
By Seter
  • 无匹配
aheadlead 说:
2012年8月30日 17:11

你的代码风格真是跪烂INT_MAX次....

111111 说:
2016年2月13日 23:13

大犇对不起。。。压到了16行。。。
#include <stdio.h>
#include <Seter>
#define maxn 200
#define maxm 200
int getint(int &re,int ch=0,bool t=1){
while(t?t=0,re=0,ch=getchar():0,ch<'0'||ch>'9')if((ch=getchar())<=0)return -1;
for(;ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
return re;}
int dis[maxn],gap[maxm+1],m=0,flow=0,n,i,d,s=0,t,x,y,z,b1,b2,t1;
struct edge{int x,t,y;struct edge *opp,*next;}*map[maxn],*neck[maxn],*from[maxn],*cur[maxn],st[maxm<<1],*p;
main(){
for(getint(i),t=getint(gap[0])-1;i?getint(x),getint(y),getint(z),st[m].next=map[st[m^1].y-1=st[m].x-1=x-1],st[m^1].next=map[st[m].y-1=st[m^1].x-1=y-1],(st[m^1].opp=map[x-1]=st+m)->z=z,st[m].opp=map[y-1]=st+(m^1),m+=2,1:0;i--);
for(i=s,m>>=1;b1=0,!b2&&dis[s]<=m?1:printf("%d",flow);){
for(cur[i]||(cur[i]=map[i]);t1=cur[i]->t&&dis[cur[i]->y]+1==dis[i],!b1&&cur[i];cur[i]=cur[i]->next)
for(t1?b1=1,neck[(from[cur[i]->y]=cur[i])->y]=s==i?cur[i]:neck[i]->t>cur[i]->t?cur[i]:neck[i],(i=cur[i]->y)==t?flow+=d=neck[t]->t:0:0;t1?(i=cur[i]->y)==t?i!=s?1:i=neck[t]->x:0:0;i=from[i]->x)from[i]->t-=d,from[i]->opp->t+=d;
for(b2=!cur[i]&&!--gap[dis[i]],!cur[i]?dis[i]=m,p=map[i]:0;!b2&&!cur[i]?p?1:gap[++dis[i]]++,i=i==s?s:from[i]->x:0;p=p->next)dis[i]=p->t&&dis[p->y]<dis[i]?dis[(cur[i]=p)->y]:dis[i];}}


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee