HDU 3549 Flow Problem(最大流入门)
http://acm.hdu.edu.cn/showproblem.php?pid=3549
题意:
给你一个N个顶点M条边的有向图,要你求1号点到N号点的最大流.
分析:
注意本题有重边.
网络流的第一道题,3种模板都用来验证一遍.
AC代码: Edmonds_Karp算法
#include
#include
#include
#include
#define INF 1e9
using namespace std;
const int maxn=15+5;
struct Network_flow
{
int n; //总节点数
int flow[maxn][maxn]; //当前流量
int cap[maxn][maxn]; //容量
void init(int n)
{
this->n=n;
memset(cap,0,sizeof(cap));
}
int solve(int s,int t)
{
queue q;
memset(flow,0,sizeof(flow));
int ans=0; //最大流
int a[maxn];//a[i]表从s到i点的最小残量
int p[maxn];//增广路上一节点
while(true)
{
memset(a,0,sizeof(a));
a[s]=INF;
q.push(s);
while(!q.empty())
{
int u=q.front(); q.pop();
for(int v=1;v<=n;v++)if(!a[v] && cap[u][v]>flow[u][v])
{
p[v]=u;
q.push(v);
a[v]=min(a[u], cap[u][v]-flow[u][v]);
}
}
if(a[t]==0) break;
for(int u=t; u!=s; u=p[u])
{
flow[p[u]][u] +=a[t];
flow[u][p[u]] -=a[t];
}
ans +=a[t];
}
return ans;
}
}EK;//Edmonds_Karp算法
int main()
{
int T; scanf("%d",&T);
for(int kase=1; kase<=T; ++kase)
{
int n,m;
scanf("%d%d",&n,&m);
EK.init(n);
while(m--)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
EK.cap[u][v] +=w;//注意:有重边
}
printf("Case %d: %d\n",kase,EK.solve(1,n));
}
return 0;
}
AC代码二: Dinic vector邻接表实现 (写这里的时候无限TLE,结果发现自己maxn开成了10+5大小..)
#include
#include
#include
#define INF 1e9
using namespace std;
const int maxn=15+5;//之前这里只写10+5,一直TLE,真是悲剧
struct Edge
{
Edge(){}
Edge(int from,int to,int cap,int flow):from(from),to(to),cap(cap),flow(flow){}
int from,to,cap,flow;
};
struct Dinic
{
int n,m,s,t; //结点数,边数(包括反向弧),源点与汇点编号
vector edges; //边表 edges[e]和edges[e^1]互为反向弧
vector G[maxn]; //邻接表,G[i][j]表示结点i的第j条边在e数组中的序号
bool vis[maxn]; //BFS使用,标记一个节点是否被遍历过
int d[maxn]; //从起点到i点的距离
int cur[maxn]; //当前弧下标
void init(int n,int s,int t)
{
this->n=n,this->s=s,this->t=t;
for(int i=1;i<=n;i++) G[i].clear();
edges.clear();
}
void AddEdge(int from,int to,int cap)
{
edges.push_back( Edge(from,to,cap,0) );
edges.push_back( Edge(to,from,0,0) );
m = edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool BFS()
{
memset(vis,0,sizeof(vis));
queue Q;//用来保存节点编号的
Q.push(s);
d[s]=0;
vis[s]=true;
while(!Q.empty())
{
int x=Q.front(); Q.pop();
for(int i=0; ie.flow)
{
vis[e.to]=true;
d[e.to] = d[x]+1;
Q.push(e.to);
}
}
}
return vis[t];
}
int DFS(int x,int a)
{
if(x==t || a==0)return a;
int flow=0,f;//flow用来记录从x到t的最小残量
for(int& i=cur[x]; i0 )
{
e.flow +=f;
edges[G[x][i]^1].flow -=f;
flow += f;
a -= f;
if(a==0) break;
}
}
return flow;
}
int Maxflow()
{
int flow=0;
while(BFS())
{
memset(cur,0,sizeof(cur));
flow += DFS(s,INF);
}
return flow;
}
}DC;
int main()
{
int T; scanf("%d",&T);
for(int kase=1; kase<=T; ++kase)
{
int n,m;
scanf("%d%d",&n,&m);
DC.init(n,1,n);
while(m--)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
DC.AddEdge(u,v,w);
}
printf("Case %d: %d\n",kase,DC.Maxflow());
}
return 0;
}
AC代码三: Dinic邻接表数组实现
#include
#include
#include
#define INF 1e9
using namespace std;
const int maxn=15+5;
const int maxm=2000+10;
struct Edge
{
Edge(){}
Edge(int from,int to,int cap,int flow):from(from),to(to),cap(cap),flow(flow){}
int from,to,cap,flow;
};
struct Dinic
{
int n,m,s,t; //结点数,边数(包括反向弧),源点与汇点编号
Edge edges[maxm]; //边表 edges[e]和edges[e^1]互为反向弧
int head[maxn],next[maxm]; //邻接表表头和next数组
bool vis[maxn]; //BFS使用,标记一个节点是否被遍历过
int d[maxn]; //从起点到i点的距离
int cur[maxn]; //当前弧下标
void init(int n,int s,int t)
{
this->n=n,this->s=s,this->t=t;
memset(head,-1,sizeof(head));
m=0;
}
void AddEdge(int from,int to,int cap)
{
edges[m]= Edge(from,to,cap,0) ;
next[m]=head[from];
head[from]=m++;
edges[m]= Edge(to,from,0,0) ;
next[m]=head[to];
head[to]=m++;
}
bool BFS()
{
memset(vis,0,sizeof(vis));
queue Q;//用来保存节点编号的
Q.push(s);
d[s]=0;
vis[s]=true;
while(!Q.empty())
{
int x=Q.front(); Q.pop();
for(int i=head[x]; i!=-1; i=next[i])
{
Edge& e=edges[i];
if(!vis[e.to] && e.cap>e.flow)
{
vis[e.to]=true;
d[e.to] = d[x]+1;
Q.push(e.to);
}
}
}
return vis[t];
}
int DFS(int x,int a)
{
if(x==t || a==0)return a;
int flow=0,f;//flow用来记录从x到t的最小残量
for(int& i=cur[x]; i!=-1; i=next[i])
{
Edge& e=edges[i];
if(d[x]+1==d[e.to] && (f=DFS( e.to,min(a,e.cap-e.flow) ) )>0 )
{
e.flow +=f;
edges[i^1].flow -=f;
flow += f;
a -= f;
if(a==0) break;
}
}
return flow;
}
int Maxflow()
{
int flow=0;
while(BFS())
{
for(int i=1;i<=n;i++) cur[i]=head[i];
flow += DFS(s,INF);
}
return flow;
}
}DC;
int main()
{
int T; scanf("%d",&T);
for(int kase=1; kase<=T; ++kase)
{
int n,m;
scanf("%d%d",&n,&m);
DC.init(n,1,n);
while(m--)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
DC.AddEdge(u,v,w);
}
printf("Case %d: %d\n",kase,DC.Maxflow());
}
return 0;
}