poj1149 最大流

2024-04-28 17:18

文章标签 最大 poj1149

本文主要是介绍poj1149 最大流，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原文：http://wenku.baidu.com/view/0ad00abec77da26925c5b01c.html

下面贴上自己的代码：

邻接矩阵的Dinic

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 110
#define MAXM 1005
#define inf 0x0fffffff
#define Min(a,b)(a<b?a:b)

int pig[MAXM];
int G[MAXN][MAXN];
int M,N;
int vis[MAXM]; //vis[t]第一次访问t猪圈的顾客编号
int level[MAXN];
int iter[MAXN];

void bfs(int s)
{
memset(level,-1,sizeof(level));
queue<int>que;
que.push(s);
level[s]=0;
while(!que.empty())
{
  int v=que.front();
  que.pop();
  int i;
  for(i=1;i<=N+2;i++)
   if(G[v][i]>0&&level[i]==-1)
   {
    level[i]=level[v]+1;
    que.push(i);
   }
}
}

int dfs(int v,int t,int f)
{
if(v==t)
  return f;
for(int &i=iter[v];i<=N+2;i++)
  if(G[v][i]>0&&level[v]<level[i])
  {
   int d=dfs(i,t,Min(f,G[v][i]));
   if(d>0)
   {
    G[v][i]-=d;
    G[i][v]+=d;
    return d;
   }
  }
return 0;
}
int max_flow(int s,int t)
{
int flow=0;
while(1)
{
  bfs(s);
  if(level[t]<0)
   return flow;
  memset(iter,0,sizeof(iter));
  int f;
  while((f=dfs(s,t,inf))>0)
  {
   flow+=f;
  }
}
}
int main()
{
// freopen("C:\\1.txt","r",stdin);
cin>>M>>N;
int st=N+1;
int ed=N+2;
int i,j,A;
for(i=1;i<=M;i++)
  scanf("%d",&pig[i]);
for(i=1;i<=N;i++)
{
  cin>>A;
  for(j=1;j<=A;j++)
  {
   int t;
   scanf("%d",&t);
   if(!vis[t]) //如果这个猪圈是第一次访问 st->i加一条pig[t]流量的边
   {
    G[st][i]+=pig[t];
    vis[t]=i; //第一次访问的节点编号
   }
   else    //被之前的顾客访问过，从第一次访问t的顾客vis[t]->i连一条inf的边
   {
    G[vis[t]][i]=inf;
   }
  }
  int B;
  scanf("%d",&B);
  G[i][ed]=B;
}
printf("%d\n",max_flow(st,ed));
}