  Dinic
#include<iostream>
#define MAXN 201
using namespace std;
struct edge
{
int st,ed;
int next;
int c;
}e[2*MAXN];
int n,m;
int E=0;
int head[MAXN],d[MAXN];
bool bfs(int s)
{
memset(d,-1,sizeof(d));
int que[MAXN],rear=1;
que[0]=s;
int i,j;
d[s]=0;
for(i=0;i<rear;i++)
{
for(j=head[que[i]];j!=-1;j=e[j].next)
{
if(d[e[j].ed]==-1&&e[j].c>0)
{
d[e[j].ed]=d[que[i]]+1;
que[rear++]=e[j].ed;
}
}
}
if(d[m]<0)
return 0;
return 1;
}
int dinic(int t,int sum)
{
if(t==m)
return sum;
int i;
int os=sum;
for(i=head[t];i!=-1;i=e[i].next)
{
if(d[e[i].ed]==d[t]+1&&e[i].c>0)
{
int a=dinic(e[i].ed,min(sum,e[i].c));
e[i].c-=a;
e[i^1].c+=a;
sum-= a;
}
}
return os-sum;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
int i;
int a,b,c;
E=0;
memset(head,-1,sizeof(head));
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&a,&b,&c);
e[E].st=a;
e[E].ed=b;
e[E].c=c;
e[E].next=head[a];
head[a]=E++;
e[E].st=b;
e[E].ed=a;
e[E].c=0;
e[E].next=head[b];
head[b]=E++;
}
int res=0;
while(bfs(1))
{
int flow;
flow=dinic(1,INT_MAX);
res+=flow;
}
printf("%d\n",res);
}
system("pause");
return 0;
}
ISAP+GAP+當(dāng)前弧+鄰接矩陣
#include<iostream>
#define maxn 300
const int inf=1000000000;
using namespace std;
int f[maxn][maxn];
int d[maxn];
int numb[maxn];
int pi[maxn];
int start[maxn];
int n,m;
int source,sink;
void Init()
{
memset(pi,0,sizeof(pi));
memset(f,0,sizeof(f));
return ;
}
void BFS()
{
int i,j;
for(i=1;i<=n;i++)
{
d[i]=n;
numb[i]=0;
}
int Q[maxn],head(0),tail(0);
d[sink]=0;
numb[0]=1;
Q[++tail]=sink;
while(head<tail)
{
i=Q[++head];
for(j=1;j<=n;j++)
{
if(f[j][i]==0||d[j]<n)
continue;
d[j]=d[i]+1;
numb[d[j]]++;
Q[++tail]=j;
}
}
return ;
}
int Augment()
{
int i,j;
int tmp=inf;
for(i=sink,j=pi[i];i!=source;i=j,j=pi[j])
{
if(tmp>f[j][i])
tmp=f[j][i];
}
for(i=sink,j=pi[i];i!=source;i=j,j=pi[j])
{
f[j][i]-=tmp;
f[i][j]+=tmp;
}
return tmp;
}
int Retreat(int &i)
{
int tmp,j,mind(n-1);
for(j=1;j<=n;j++)
{
if(f[i][j]>0&&d[j]<mind)
mind=d[j];
}
tmp=d[i];
d[i]=mind+1;
numb[tmp]--;
numb[d[i]]++;
if(i!=source)
i=pi[i];
return numb[tmp];
}
int maxflow()
{
int flow(0),i,j;
BFS();
for(i=1;i<=n;i++)
start[i]=1;
i=source;
while(d[source]<n)
{
for(j=start[i];j<=n;j++)
if(f[i][j]>0&&d[i]==d[j]+1)
break;
if(j<=n)
{
start[i]=j;
pi[j]=i;
i=j;
if(i==sink)
{
flow+=Augment();
i=source;
}
}
else
{
start[i]=1;
if(Retreat(i)==0)
break;
}
}
return flow;
}
int main()
{
int i,j;
int a,b,c;
while(scanf("%d%d",&m,&n)==2)
{
source=1;
sink=n;
Init();
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
f[a][b]+=c;
}
printf("%d\n",maxflow());
}
system("pause");
return 0;
}
ISAP+GAP+當(dāng)前弧+鄰接表(雙向鏈表)
#include<iostream>
#define maxn 300
const int inf=1000000000;
using namespace std;
struct edge
{
int u,v,next,f,pre;
}e[2*maxn];
int num,rnum;
int head[maxn],rhead[maxn];
int d[maxn];
int numb[maxn];
int start[maxn];
int n,m;
int p[maxn];
int source,sink;
void Init()
{
memset(head,-1,sizeof(head));
memset(rhead,-1,sizeof(rhead));
memset(p,-1,sizeof(p));
num=0;
return ;
}
void BFS()
{
int i,j;
for(i=1;i<=n;i++)
{
d[i]=n;
numb[i]=0;
}
int Q[maxn],head(0),tail(0);
d[sink]=0;
numb[0]=1;
Q[++tail]=sink;
while(head<tail)
{
i=Q[++head];
for(j=rhead[i];j!=-1;j=e[j].pre)
{
if(e[j].f==0||d[e[j].u]<n)
continue;
d[e[j].u]=d[i]+1;
numb[d[e[j].u]]++;
Q[++tail]=e[j].u;
}
}
return ;
}
int Augment()
{
int i;
int tmp=inf;
for(i=p[sink];i!=-1;i=p[e[i].u])
{
if(tmp>e[i].f)
tmp=e[i].f;
}
for(i=p[sink];i!=-1;i=p[e[i].u])
{
e[i].f-=tmp;
e[i^1].f+=tmp;
}
return tmp;
}
int Retreat(int &i)
{
int tmp,j,mind(n-1);
for(j=head[i];j!=-1;j=e[j].next)
{
if(e[j].f>0&&d[e[j].v]<mind)
mind=d[e[j].v];
}
tmp=d[i];
d[i]=mind+1;
numb[tmp]--;
numb[d[i]]++;
if(i!=source)
i=e[p[i]].u;
return numb[tmp];
}
int maxflow()
{
int flow(0),i,j;
BFS();
for(i=1;i<=n;i++)
start[i]=head[i];
i=source;
while(d[source]<n)
{
for(j=start[i];j!=-1;j=e[j].next)
if(e[j].f>0&&d[i]==d[e[j].v]+1)
break;
if(j!=-1)
{
start[i]=j;
p[e[j].v]=j;
i=e[j].v;
if(i==sink)
{
flow+=Augment();
i=source;
}
}
else
{
start[i]=head[i];
if(Retreat(i)==0)
break;
}
}
return flow;
}
void addedge(int a,int b,int c)
{
e[num].next=head[a];
head[a]=num;
e[num].pre=rhead[b];
rhead[b]=num;
e[num].f=c;
e[num].u=a;
e[num++].v=b;
e[num].next=head[b];
head[b]=num;
e[num].pre=rhead[a];
rhead[a]=num;
e[num].u=b;
e[num].v=a;
e[num++].f=0;
return ;
}
int main()
{
int i;
int a,b,c;
while(scanf("%d%d",&m,&n)==2)
{
source=1;
sink=n;
Init();
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);
}
printf("%d\n",maxflow());
}
system("pause");
return 0;
}
|