Posted on 2010-08-18 16:26
acronix 阅读(353)
评论(0) 编辑 收藏 引用 所属分类:
hzshuai收集的模板
朴素的最大流代码：
//BOJ 1154
#include <cstdio>
const int inf = 1<<25;
int cap[205][205];
int pre[205],s,t,i,j,n,m,x,y,v,que[205];
bool vis[205];
/***********************************************/
bool bfs()
{
for (i = 1; i <= m; i++)
vis[i] = false;
int f = 0,r = 1,st;
que[r] = s; vis[1] = true;
while (f < r)
{
st = que[++f];
for (i = 1; i<= m; i++)
if (vis[i] != true && cap[st][i] > 0)
{
pre[i] = st;
vis[i] = true;
if (i == t)
return true;
que[++r] = i;
}
}
return false;
}
int max_flow()
{
int sum = 0,min;
while (bfs())
{
min = inf;
i = t;
while (i != s)
{
if (cap[pre[i]][i] < min)
min = cap[pre[i]][i];
i = pre[i];
}
i = t;
sum += min;
while (i != s)
{
cap[pre[i]][i] -= min;
cap[i][pre[i]] += min;
i = pre[i];
}
}
return sum;
}
/*****************************************************************/
int main()
{
while (scanf("%d %d",&n,&m) != EOF)
{
for (i = 1;i <= m; i++)
for (j = 1; j <= m; j ++)
cap[i][j] = 0;
for (i = 1; i <= n; i++)
{
scanf("%d %d %d",&x,&y,&v);
cap[x][y] += v;
}
s = 1; t = m;
printf("%d\n",max_flow());
}
return 0;
}
Dinic 的最大流代码：
#include<iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
/************Dinic**********************/
#define Max 210
int flow[Max][Max],d[Max]; //flow is the network
int sta,end,N; //sta is the sourse ,end is the end,N is the number of vector
bool bfs(int s)
{
int front=0,rear=0;
int q[Max];
memset(d,-1,sizeof(d)); //d[] is the deep
q[rear++]=s; d[s]=0;
while(front<rear)
{
int k=q[front++];
for(int i=0;i<=N;i++)
if(flow[k][i]>0&&d[i]==-1){
d[i]=d[k]+1;
q[rear++]=i;
}
}
if(d[end]>=0) return true;
return false;
}
int dinic(int k,int sum) //k is the sourse
{
if (k==end) return sum;
int os = sum;
for(int i=0;i<=N&∑i++)
if(d[i]==d[k]+1&&flow[k][i]>0)
{
int a=dinic(i,min(sum,flow[k][i])); //Deep to the end.
flow[k][i]-=a;
flow[i][k]+=a;
sum -= a;
}
return os-sum;
}
/*******************************************/
int main()
{
int n,x,y,v;
while (scanf("%d %d",&n,&N) != EOF)
{
memset(flow,0,sizeof(flow));
for (int i = 1; i <= n; i++)
{
scanf("%d %d %d",&x,&y,&v);
flow[x][y] += v;
}
/**********************/
int ret=0;
sta = 1; end = N;
while(bfs(sta))
ret += dinic(sta,0x7ffffff);
/***************************/
printf("%d\n",ret);
}
return 0;
}