【POJ 1459 power network】

不可以理解的是,测评站上的0ms是怎么搞出来的。

这一题在建立超级源点和超级汇点后就变得温和可爱了。其实它本身就温和可爱。对比了能够找到的题解:

(1)艾德蒙·卡普算法(2)迪尼克算法(3)改进版艾德蒙·卡普算法(MY METHOD)

不去管那个0ms的吧,那么(3)号算法最为美妙【它的别名是:ISAP】,时间可观。

这个就算是一个ISAP的模板吧(除了输入的难看的几行外,其余均是标准的大米饼牌模板!)

 #include<stdio.h>
#include<algorithm>
#include<queue>
#include<cstring>
#define go(i,a,b) for(int i=a;i<=b;i++)
#define fo(i,a,x) for(int i=a[x],v=e[i].v;i>-1;i=e[i].next,v=e[i].v)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;const int N=
;
struct E{int v,next,flow,cap;}e[N*
N];
int n,n_power,n_user,m,S,T,head[N],k=
,d[N];
int
num[N],cur[N],preE[N],preN[N];
void ADD(int u,int v,int flow,int cap){e[k]=(E){v,head[u],flow,cap};head[u]=k++;}
void
BFS()
{
queue<int>q;bool vis[N]={};q.push(T);d[T]=
;
while(!
q.empty())
{
int u=
q.front();q.pop();
fo(i,head,u)if(!e[i].cap&&!
vis[v])
vis[v]=,d[v]=d[u]+
,q.push(v);
}
}
int aug(){int u,a=
;
u=T;while(u!=S){int i=preE[u];a=min(a,e[i].cap-e[i].flow);u=
preN[u];}
u=T;while(u!=S){int i=preE[u];e[i].flow+=a;e[i^].flow-=a;u=preN[u];}return
a;}
int main(){while(~scanf("%d%d%d%d",&n,&n_power,&n_user,&
m))
{
S=;T=n+;char _;mem(head,-
);
go(i,,m){int u,v,cap;scanf(" %c%d%c%d%c%d",&_,&u,&_,&v,&_,&
cap);
u++,v++;ADD(u,v,,cap);ADD(v,u,,
);}
go(i,,n_power){int v,cap;scanf(" %c%d%c%d",&_,&v,&_,&
cap);
v++;ADD(S,v,,cap);ADD(v,S,,
);}
go(i,,n_user){int u,cap;scanf(" %c%d%c%d",&_,&u,&_,&
cap);
u++;ADD(u,T,,cap);ADD(T,u,,);}BFS();mem(num,
); go(i,,n+)num[d[i]]++,cur[i]=head[i];
int u=S,flow=
;
while(d[S]<T+
)
{
u==T?flow+=aug(),u=S:;bool retreat=
;
fo(i,cur,u) if(e[i].cap>e[i].flow&&d[u]==d[v]+
)
{retreat=;cur[u]=preE[v]=i;preN[v]=u;u=v;break
;} if(!retreat)continue; int Min=T;fo(i,head,u){if(e[i].cap>e[i].flow)Min=min(Min,d[v]);}
if(!(--num[d[u]]))break;num[d[u]=Min+]++
;
cur[u]=head[u];u==S?:u=
preN[u];
}
printf("%d\n"
,flow);
}return ;}//Paul_Guderian

【改进版艾德蒙·卡普算法】

网络流两个学习要点:学会转化问题,学会几个模型?你是在质疑神奇大米饼的权威吗?那就给你个大米饼!

ZBH不给我玩以撒的结合…我写了这篇博客来表达愤怒!

上一篇:4.hive的外部表和内部表


下一篇:android开源项目和框架