【移动应用开发技术】高效的最大流sap+邻接表模版

【移动应用开发技术】高效的最大流sap+邻接表模版

/*最大流模板isap复杂度(v^2*e)*//**State:

HDU4280

3609MS

8860K

3571

B

C++*题目大意：*

有N个岛屿

M条无向路

每个路有一最大允许的客流量，求从最西的那个岛屿最多能运*

用多少乘客到最东的那个岛屿。*解题思路：*

很单纯的网络流，重点是卡时间

模板的高效性很重要啊该模板详解*

参见这里

模板题就不注释了*解题感想：*

10000ms的时间里，大多数最大流算法都挂掉了，就这个坚持下来了，用了3000ms左右。*/#include

<stdio.h>#include

<iostream>#include

<string.h>#define

VM

100010#define

EM

400010using

namespace

std;const

int

inf

=

0x3f3f3f3f;struct

E{

int

to,

frm,

nxt,

cap;}edge[EM];int

head[VM],

e;//建图时初始化int

dep[VM],

gap[VM];//ISAP函数内初始化void

init(){

e

=

0;

memset(head,

-1,

sizeof(head));}void

addEdge(int

cu,

int

cv,

int

cw){

edge[e].frm

=

cu;

edge[e].to

=

cv;

edge[e].cap

=

cw;

edge[e].nxt

=

head[cu];

head[cu]

=

e++;

edge[e].frm

=

cv;

edge[e].to

=

cu;

edge[e].cap

=

0;

edge[e].nxt

=

head[cv];

head[cv]

=

e++;}int

que[VM];void

BFS(int

des){

memset(dep,

-1,

sizeof(dep));

memset(gap,

0,

sizeof(gap));

gap[0]

=

1;

int

front

=

0,

rear

=

0;

dep[des]

=

0;

que[rear++]

=

des;

int

u,

v;

while

(front

!=

rear)

{

u

=

que[front++];

front

=

front%VM;

for

(int

i=head[u];

i!=-1;

i=edge[i].nxt)

{

v

=

edge[i].to;

if

(edge[i].cap

!=

0

||

dep[v]

!=

-1)

continue;

que[rear++]

=

v;

rear

=

rear

%

VM;

++gap[dep[v]

=

dep[u]

+

1];

}

}}int

cur[VM],

stack[VM];//sap模板int

ISAP(int

src,

int

des,

int

n)//源点、汇点、图中点的总数

{

int

res

=

0;

BFS(des);

int

top

=

0;

memcpy(cur,

head,

sizeof(head));

int

u

=

src,

i;

while

(dep[src]

<

n)

{

if

(u

==

des)

{

int

temp

=

inf,

inser

=

n;

for

(i=0;

i!=top;

++i)

if

(temp

>

edge[stack[i]].cap)

{

temp

=

edge[stack[i]].cap;

inser

=

i;

}

for

(i=0;

i!=top;

++i)

{

edge[stack[i]].cap

-=

temp;

edge[stack[i]^1].cap

+=

temp;

}

res

+=

temp;

top

=

inser;

u

=

edge[stack[top]].frm;

}

if

(u

!=

des

&&

gap[dep[u]

-1]

==

0)

break;

for

(i

=

cur[u];

i

!=

-1;

i

=

edge[i].nxt)

if

(edge[i].cap

!=

0

&&

dep[u]

==

dep[edge[i].to]

+

1)

break;

if

(i

!=

-1)

{

cur[u]

=

i;

stack[top++]

=

i;

u

=

edge[i].to;

}

else

{

int

min

=

n;

for

(i

=

head[u];

i

!=

-1;

i

=

edge[i].nxt)

{

if

(edge[i].cap

==

0)

continue;

if

(min

>

dep[edge[i].to])

{

min

=

dep[edge[i].to];

cur[u]

=

i;

}

}

--gap[dep[u]];

++gap[dep[u]

=

min

+

1];

if

(u

!=

src)

u

=

edge[stack[--top]].frm;

}

}

return

res;}int

main(){#ifndef

ONLINE_JUDGE

freopen("in.txt",

"r",

stdin);#endif

int

n,

m,

T;

scanf("%d",

&T);

while

(T--)

{

scanf("%d

%d",

&n,

&m);

int

x,

y,

src,

des;

int

Min

=

inf,

Max

=

-inf;

for

(int

i

=

1;

i

<=

n;

++i)

//找出起点src

终点des

{

scanf("%d

%d",

&x,

&y);

if

(x

<=

Min)

{

src

=

i;

Min

=

x;

}

if

(x

>=

Max)

{

des

=

i;

Max

=

x;

}

}

init();

int

u,

v,

c;

for

(int

i

=

0;

i

!=

m;

++i)

{

scanf("%d

%d

%d",

&u,

&v,

&c);

addEdge(u,

v,

c);

addEdge(v,

u,

c);

}

int

ans

=

ISAP(src,

des,

n);

printf("%d\n",

ans);

}

return

0;}

//Isap邻接矩阵版模板//HDU3549

Isap邻接矩阵版//46ms#include

<iostream>#include

<cstring>#include

<cstdio>#define

M

16using

namespace

std;const

int

inf

=

0x3f3f3f3f;int

maze[M][M];int

gap[M],dis[M],pre[M],cur[M];void

init(){

memset(maze,

0,

sizeof(maze));}//起点是0，

终点是n-1,nodenum为点的个数int

ISAP(int

s,

int

t,

int

nodenum)

{

memset(cur,

0,

sizeof(cur));

memset(dis,

0,

sizeof(dis));

memset(gap,

0,

sizeof(gap));

int

u

=

pre[s]

=

s,maxflow

=

0,aug

=

inf;

gap[0]

=

nodenum;

while(dis[s]

<

nodenum)

{loop:

for(int

v

=

cur[u];

v

<

nodenum;

v++)

if(maze[u][v]

&&

dis[u]

==

dis[v]

+

1)

{

aug

=

min(aug,

maze[u][v]);

pre[v]

=

u;

u

=

cur[u]

=

v;

if(v

==

t)

{

maxflow

+=

aug;

for(u

=

pre[u];v

!=

s;v

=

u,u

=

pre[u])

{

maze[u][v]

-=

aug;

maze[v][u]

+=

aug;

}

aug

=

inf;

}

goto

loop;

}

int

mindis=

nodenum-1;

for(int

v

=

0;

v

<

nodenum;

v++)

if(maze[u][v]

&&

mindis>

dis[v])

{

cur[u]

=

v;

mindis=

dis[v];

}

if((--gap[dis[u]])==

0)

break;

gap[dis[u]

=

mindis+1]

++;

u

=

pre[u];

}

return

maxflow;}int

main(void){#ifndef

ONLINE_JUDGE

freopen("HDU3549.txt",

"r",

stdin);#endif

int

n,

m,

cas,

cas_c

=

1;

scanf("%d",

&cas);

while(cas--)

{

scanf("%d

%d",

&n,

&m);

init();

int

u,

v,

w;

for(int

i

=

0;

i

<

m;

i++)

{

scanf("%d

%d

%d",

&u,

&v,

&w);

u--,

v--;

maze[u][v]

+=

w;

}

int

sol

=

ISAP(0,

n-1,

n);//起点，终点

printf("Case

%d:

%d\n",

cas_c++,

sol);

}

return

0;}

//State:

HDU4280居然用了2700ms+,牛逼模版/*

This

Problem

beat

me

completely.

Beat

my

template

completely.

Beat

my

funtion

comletely.

Waste

my

time

comletely.

It's

a

naked

maximum-stream

problem.

The

main

point

is

your

template.

It

make

me

realize

that

my

SAP

template

is

a

sh*t!

To

make

my

SAP

faster,

I

have

done

three

kinds

of

optimization.

1.

Record

the

adjacency

node

which

has

minimum

distance;

2.

Initailize

the

distance

by

using

BFS;

3.

As

I

got

a

Stack-Overflow,

I

simulate

the

DFS

by

using

stack

in

STL;

Then

I

got

AC

in

2s+.

Of

course,

the

problem

is

also

correspond

to

the

Minimum-Cut

in

Dual-Graph.

Hence,

Dijkstra

with

minimum

heap

is

optimal

algorithm.

*///Header//#include

<cstdio>//#include

<cstdlib>//#include

<iostream>//#include

<cstring>//#include

<string>//#include

<vector>//#include

<map>//#include

<algorithm>//#include

<cctype>//#include

<queue>//#include

<stack>//#include

<cmath>//using

namespace

std;////Macro////STL-Alias//#define

UN(c,

a)

unique(c,

a)//#define

MS(c,

a)

memset(c,

a,

sizeof

c)//#define

FLC(c,

a

,b)

fill(c,

c

+

a,

b)//#define

LOS(c,

a,

b)

lower_bound(c,

a,

b)//#define

UPS(c,

a,

b)

upper_bound(c,

a,

b)////Syntax-Alias//#define

Rep(c,

a,

b)

for

(int

c

=

(a);

c

<

(b);

c++)//#define

Nre(c,

a,

b)

for

(int

c

=

(a);

c

>

(b);

c--)////DEBUG//#define

FK

puts("Fu*k

here!")//#define

PA(s,

c,

a,

b,

p,

f){\//

printf(s);\//

Rep(c,

a,

b)

printf(p,

(f));\//

puts("");}////Constant//#define

INFL

(0x7fffffffffffffffLL)//#define

INFI

(0x7fffffff)//#define

MOD

()//#define

MAXN

(100005)////Type-Alias//typedef

long

long

LL;//typedef

long

double

LD;//typedef

int

AI[MAXN];//typedef

bool

AB[MAXN];//typedef

double

AD[MAXN];//typedef

LL

ALL[MAXN];//typedef

LD

ALD[MAXN];////////FSG//struct

Edge//{//

int

v,

w,

next;//};//vector<Edge>

E;//AI

L;//void

G_ini()//{//

E.clear();//

MS(L,

-1);//}//void

AE(int

u,

int

v,

int

w)//{//

Edge

te

=

{v,

w,

L[u]};//

L[u]

=

E.size();//

E.push_back(te);//}//#define

Ere(c,

a,

L)

for

(int

c

=

L[a];

c

!=

-1;

c

=

E[c].next)////////ISAP//int

ISAP(int

src,

int

snk,

int

V)//{//

static

AI

dis,

gap,

_L,

se;//

int

u

=

src,

mxf

=

0,

te

=

0;//

memcpy(_L,

L,

sizeof

L);//

MS(dis,

-1);

MS(gap,

0);//

gap[dis[snk]

=

0]

=

1;//

queue<int>

Q;//

Q.push(snk);//

while

(!Q.empty())//

{//

int

u

=

Q.front();

Q.pop();//

Ere(i,

u,

L)

if

(E[i].w

&&

dis[E[i].v]

<

0)//

{//

gap[dis[E[i].v]

=

dis[u]

+

1]++;//

Q.push(E[i].v);//

}//

}//

while

(dis[src]

<

V)//

{//

int

_i

=

-1;//

Ere(i,

u,

_L)

if

(E[i].w

&&

dis[u]

==

dis[E[i].v]

+

1)//

{//

_i

=

i;//

break;//

}//

if

(_i

!=

-1)//

{//

_L[u]

=

_i;//

u

=

E[se[te++]

=

_i].v;//

}//

else//

{//

int

md

=

INFI;//

_i

=

-1;//

Ere(i,

u,

L)

if

(E[i].w

&&

dis[E[i].v]

<

md)//

{//

md

=

dis[E[i].v];//

_L[u]

=

i;//

}//

if

(!--gap[dis[u]])

break;//

gap[dis[u]

=

md

+

1]++;//

if

(u

!=

src)

u

=

E[se[te--

-

1]

^

1].v;//

}//

if

(u

==

snk)//

{//

int

_i

=

0,

mf

=

INFI;//

Rep(i,

0,

te)

if

(E[se[i]].w

<

mf)//

{//

mf

=

E[se[i]].w;//

_i

=

i;//

}//

Rep(i,

0,

te)//

{//

E[se[i]].w

-=

mf;//

E[se[i]

^

1].w

+=

mf;//

}//

mxf

+=

mf;//

te

=

_i;//

u

=

E[se[_i]

^

1].v;//

}//

}//

return

mxf;//}//////struct

Isl//{//

int

x,

y;//

void

inp()//

{//

scanf("%d%d",

&x,

&y);//

}//}

I[MAXN];//int

n,

m;//////int

main()//{//

int

T;//

scanf("%d",

&T);//

while

(T--)//

{//

//Initialize//

scanf("%d%d",

&n,

&m);//

I[0].inp();//

int

src

=

0,

snk

=

0;//

Rep(i,

1,

n)//

{//

I[i].inp();//

if

(I[i].x

<

I[src].x)

src

=

i;//

if

(I[i].x

>

I[snk].x)

snk

=

i;//

}//

G_ini();//

while

(m--)//

{//

int

u,

v,

w;//

scanf("%d%d%d",

&u,

&v,

&w);//

u--;//

v--;//

AE(u,

v,

w);//

AE(v,

u,

w);//

}//

//Solve//

printf("%d\n",

ISAP(src,

snk,

n));//

}//

return

0;//}////////////////isap深搜版，以HDU4280长春网络赛的题目为例，不过那题10000ms都TLE////不知道dfs版有什么长处，据说dfs版比dinic要快。//#include

<iostream>//using

namespace

std;////typedef

struct

{int

v,next,val;}

edge;//const

int

MAXN=100005;//const

int

MAXM=500010;//const

int

inf

=

0x3f3f3f3f;//edge

e[MAXM];//int

p[MAXN],eid;//

//inline

void

init(){memset(p,-1,sizeof(p));eid=0;}//

////有向//inline

void

insert1(int

from,int

to,int

val)//{//

e[eid].v=to;//

e[eid].val=val;//

e[eid].next=p[from];//

p[from]=eid++;//

//

swap(from,to);//

//

e[eid].v=to;//

e[eid].val=0;//

e[eid].next=p[from];//

p[from]=eid++;//}//

////无向//inline

void

insert2(int

from,int

to,int

val)//{//

e[eid].v=to;//

e[eid].val=val;//

e[eid].next=p[from];//

p[from]=eid++;//

//

swap(from,to);//

//

e[eid].v=to;//

e[eid].val=val;//

e[eid].next=p[from];//

p[from]=eid++;//}//

//int

n,m;//n为点数

m为边数//int

h[MAXN];//int

gap[MAXN];//

//int

source,sink;//inline

int

dfs(int

pos,int

cost)//{//

if

(pos==sink)//

{//

return

cost;//

}//

//

int

j,minh=n-1,lv=cost,d;//

//

for

(j=p[pos];j!=-1;j=e[j].next)//

{//

int

v=e[j].v,val=e[j].val;//

if(val>0)//

{//

if

(h[v]+1==h[pos])//

{//

if

(lv<e[j].val)

d=lv;//

else

d=e[j].val;//

//

d=dfs(v,d);//

e[j].val-=d;//

e[j^1].val+=d;//

lv-=d;//

if

(h[source]>=n)

return

cost-lv;//

if

(lv==0)

break;//

}//

//

if

(h[v]<minh)

minh=h[v];//

}//

}//

//

if

(lv==cost)//

{//

--gap[h[pos]];//

if

(gap[h[pos]]==0)

h[source]=n;//

h[pos]=minh+1;//

++gap[h[pos]];//

}//

//

return

cost-lv;//

//}//

//int

sap(int

st,int

ed)//{//

//

source=st;//

sink=ed;//

int

ret=0;//

memset(gap,0,sizeof(gap));//

memset(h,0,sizeof(h));//

//

gap[st]=n;//

//

while

(h[st]<n)//

{//

ret+=dfs(st,INT_MAX);//

}//

//

return

ret;//}//////int

main()//{//#ifndef

ONLINE_JUDGE//

freopen("in.txt",

"r",

stdin);//#endif//

int

T;//

scanf("%d",

&T);//

while

(T--)//

{//

scanf("%d%d",

&n,

&m);//

int

x,

y;//

int

Min

=

inf,

Max

=

-inf;//

int

src,

des;//

for

(int

i=1;

i<=n;

++i)

//找出起点src

终点des//

{//

scanf("%d%d",

&x,

&y);//

if

(x

<=

Min)//

{//

src

=

i;//

Min

=

x;//

}//

if

(x

>=

Max)//

{//

des

=

i;//

Max

=

x;//

}//

}////

init();//

int

u,

v,

c;//

for

(int

i=0;

i!=m;

++i)//

{//

scanf("%d%d%d",

&u,

&v,

&c);//

//

addedge(u,v,c);//

//

addedge(v,u,c);//

insert2(u,

v,

c);//

}//

//

printf("%d\n",

sap(src,des));//

}//

return

0;//}

//邻接表——sha#include

<iostream>#include

<stdio.h>#include

<algorithm>#include

<functional>#include

<cmath>#include

<cstring>#include

<string>#include

<vector>#include

<map>#include

<set>#include

<utility>#include

<stack>#include

<queue>#include

<deque>#include

<iomanip>#define

VM

10001#define

EM

500100#define

pi

3.1415926535897932#define

abs(x)

((x)>0?(x):-(x))#define

sqr(x)

((x)*(x))#define

fill(m,v)

memset(m,v,sizeof(m))#define

SS(x)

scanf("%d",&x)#define

inf

0x7fffffff#define

hinf

0x3f3f3f3f#define

fi

first#define

se

second#define

all(x)

x.begin(),

x.end()#define

rall(v)

v.rbegin(),v.rend()#define

sz(v)

((int)v.size())#define

y0

stupid_cmath#define

y1

very_stupid_cmath#define

ll

__int64#define

ull

unsigned

__int64#define

pb

push_back#define

mp

make_pair#define

rep(i,m)

for(int

i=0;i<(int)(m);i++)#define

rep2(i,n,m)

for(int

i=n;i<(int)(m);i++)#define

FOR(i,a,b)

for(int

i

=

(a);

i

<

(b);

i++)#define

FF(i,a)

for(int

i

=

0;

i

<

(a);

i++

)#define

FFD(i,a)

for(int

i

=

(a)-1;

i

>=

0;

i--)#define

CC(m,what)

memset(m,what,sizeof(m))#define

SZ(a)

((int)a.size())#define

PP(n,m,a)

puts("");FF(i,n){FF(j,m)cout

<<

a[i][j]

<<

'

';puts("");}#define

read

freopen("in.txt","r",stdin)#define

write

freopen("out.txt","w",stdout)in