现在的位置: 首页 > 综合 > 正文

POJ1459解题报告

2018年01月20日 ⁄ 综合 ⁄ 共 2439字 ⁄ 字号 评论关闭

已经好几天没写解题报告了,今天年初一,呵呵,写一个,为今年开个好头。下面步入正题:

POJ1459这道题目的要求是求最大的消耗量。我们添加一个源点s和一个汇点t,与s相连的是所有的np(生产点),边权值为其自己能产生的数值;与t相连的是所有的nc(消耗点),边权值为其消耗最大值。至此便完成了网络的构图。然后直接套用最大流的算法模版即可解决。我使用的是EK算法。

什么是EK算法?EK算法的原理是利用BFS或者DFS每次找到网络中的一条增广路径,然后修改其流量值,直至无法找到增广路径为止。

下面给出EK的源代码:

#include <iostream>
#include <memory.h>
#include <stdio.h>
#define max 65535
using namespace std;
int s,t,n,np,nc,m,tot;
int pre[102],d[102],fx[102],f[102][102],c[102][102];
char str[50];
bool visit[102];
void init()
{
  int i,x,y,z;
  memset(f,0,sizeof(f));//f数组表示网络边的流量
  memset(c,0,sizeof(c));//c数组表示网络边的容量
  s=n;
  t=n+1;
  n+=2;
  for(i=1;i<=m;i++)
  {
    scanf("%s",&str);
    sscanf(str,"(%d,%d)%d",&x,&y,&z);
    c[x][y]=z;                
  }    
  for(i=1;i<=np;i++)
  {
    scanf("%s",&str);
    sscanf(str,"(%d)%d",&x,&z);
    c[s][x]=z;               
  }
  for(i=1;i<=nc;i++)
  {
    scanf("%s",&str);
    sscanf(str,"(%d)%d",&x,&z);
    c[x][t]=z;               
  }
  tot=0;
}
bool bfs()
{
  int i,j,head,tail,delta,x,temp,dir,y;
  head=tail=0;
  memset(d,0,sizeof(d));//队列d
  memset(visit,false,sizeof(visit));//访问标记
  memset(fx,0,sizeof(fx));//记录边的方向,若是前向边则fx[i]=1,若是逆向边fx[i]=-1
  for(i=0;i<=n;i++)//pre表示节点的前缀
    pre[i]=-1;
  d[head]=s;
  visit[s]=true;
  while(head<=tail)
  {
    x=d[head];
    for(i=0;i<=n;i++)
    if(!visit[i])
    {
      temp=0;
      dir=0;
      if(c[x][i]-f[x][i]>0)
      {
        temp=c[x][i]-f[x][i];
        dir=1;
      }
      if(f[i][x]>0&&f[i][x]>temp)
      {
        temp=f[i][x];
        dir=-1;
      }      
      if(temp>0)
      {
        pre[i]=x;
        fx[i]=dir;
        tail++;
        d[tail]=i;
        visit[i]=true; 
        if(i==t)
        {
          j=t;
          delta=max;
          while(pre[j]!=-1)//计算delta
          {
            y=pre[j];
            if(fx[j]==1)
              delta=min(delta,c[y][j]-f[y][j]);
            else
              delta=min(delta,f[j][y]); 
            j=y;         
          }
          j=t;
          while(pre[j]!=-1)//修改流量值
          {
            y=pre[j];
            if(fx[j]==1)
              f[y][j]+=delta;
            else
              f[j][y]-=delta;  
            j=y;        
          }  
          tot+=delta;   
          return true;
        }       
      }         
    }
    head++;               
  }   
  return false;
}
void deal()
{
  bool flag;
  flag=bfs();
  while(flag)
    flag=bfs();            
}
int main()
{
  while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF)
  {
    init();
    deal();
    cout<<tot<<endl;                                          
  }    
  return 0;
}

 

 

 

除EK算法外,最大流还有更好的实现方法,如SAP,DINIC,预留推进算法。。都是些很不错的算法。

最大流是网络流的基础,一定要牢牢掌握,而最大流的根本是增光路径定理和最大流最小割定理,所以一定要理解好这两个理论基础。

抱歉!评论已关闭.