POJ 1273 第一个SAP（ISAP）
/* sap学了很长时间，一直不敢下手写，结果就是不写永远不会真正的理解算法的含义，sap理论很多算法书上都有讲解，但我还是建议看数学专业 图论的书，比如 《有向图的理论，算法及应用》，这本书的内容非常棒，相信看过的都知道吧，比其他算法书上讲的透多了。SAP有个优化就是 当出现断链时，就可以直接退出，还有个优化是当前弧的优化，这两个优化只需要一句话+一个数组就解决了，相当实惠，好的ISAP执行的效率真的非常高，我写的ISAP用的是链式前向星法表示。
这个就算是模板了吧，虽然写的不是很好。。*/
#include<iostream>
#include<cstdio>
#include<memory.h>
#include<cmath>
using namespace std;
#define MAXN 500
#define MAXE 40000
#define INF 0x7fffffff
long ne,nv,tmp,s,t,index;
struct Edge{
long next,pair;
long v,cap,flow;
}edge;
long net;
long ISAP()
{
long numb,dist,curedge,pre;
long cur_flow,max_flow,u,tmp,neck,i;
memset(dist,0,sizeof(dist));
memset(numb,0,sizeof(numb));
memset(pre,-1,sizeof(pre));
for(i = 1 ; i <= nv ; ++i)
curedge = net;
numb = nv;
max_flow = 0;
u = s;
while(dist < nv)
{
/* first , check if has augmemt flow */
if(u == t)
{
cur_flow = INF;
for(i = s; i != t;i = edge].v)
{
if(cur_flow > edge].cap)
{
neck = i;
cur_flow = edge].cap;
}
}
for(i = s; i != t; i = edge].v)
{
tmp = curedge;
edge.cap -= cur_flow;
edge.flow += cur_flow;
tmp = edge.pair;
edge.cap += cur_flow;
edge.flow -= cur_flow;
}
max_flow += cur_flow;
u = neck;
}
/* if .... else ... */
for(i = curedge; i != -1; i = edge.next)
if(edge.cap > 0 && dist == dist.v]+1)
break;
if(i != -1)
{
curedge = i;
pre.v] = u;
u = edge.v;
}else{
if(0 == --numb]) break;
curedge = net;
for(tmp = nv,i = net; i != -1; i = edge.next)
if(edge.cap > 0)
tmp = tmp<dist.v]?tmp:dist.v];
dist = tmp + 1;
++numb];
if(u != s) u = pre;
}
}
return max_flow;
}
int main() {
long i,j,np,nc,m,n;
long a,b,val;
long g;
while(scanf("%d%d",&ne,&nv)!=EOF)
{
s = 1;
t = nv;
memset(g,0,sizeof(g));
memset(net,-1,sizeof(net));
for(i=0;i<ne;++i)
{
scanf("%ld%ld%ld",&a,&b,&val);
g += val;
}
for(i=1;i<=nv;++i)
for(j = i; j <= nv;++j)
if(g||g)
{
edge.next = net;
edge.v = j;
edge.cap = g;
edge.flow = 0;
edge.pair = index+1;
net = index++;
edge.next = net;
edge.v = i;
edge.cap = g;
edge.flow = 0;
edge.pair = index-1;
net = index++;
}
printf("%ld\n",ISAP());
}
return 0;
}
页:
[1]