[セットトップ]ネットワークストリームDINIC拡張アルゴリズムの紹介

ネットワークストリームDINIC拡張アルゴリズム
【アルゴリズム説明】:まず構図を作り,ノード間の容量と流量を記録する.次に、構築階層図<キューで実現され、まず1を加え、キューヘッダ要素xを取るたびに、それに隣接する点yを列挙し、階層図の性質に基づいて、xからyに容量があるか否かを判断し、d[x]+1がd[y]より小さいか否かを判断するたびに、d[y]をd[x]+1に更新し、yをキューに追加し、キュー内の要素がM個あれば、構築図完了を説明する)、DINICネットワークフローアルゴリズムを行う.再帰的に拡張路を求めるが,更新時に初期点のd値+1が到達点に等しいか否かを判断する<ここではDINICアルゴリズムによる通常の拡張路アルゴリズムの最適化である>
【タイトル】:POJ 1273とUSACO 4.2.1
<問題解決リンク>:
USACO Training 4.2.1 Drainage Ditches芝生排水問題解と分析<ネットワークフローDINICアルゴリズム>
POJ 1273 Drainage Ditches問題解と分析<ネットワークストリームDINIC>
【コード】:(USACO 4.2.1を例に)

/*
   ID:csyzcyj1
   PROG:ditch
   LANG:C++
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define MAX 201
#define IMAX 2147483647
struct LAKE{vector<int> link;};
LAKE a[MAX];
int N,M,map[MAX][MAX],ans=0,use;//map     
int d[MAX];//d     
bool build()//      
{
      int q[MAX],tot=0;
      for(int i=0;i<=M+1;i++)
            d[i]=IMAX;
      q[++tot]=1;
      d[1]=0;
      for(int i=1;i<=tot;i++)
      {
            int now=q[i];
            for(int j=0;j<a[now].link.size();j++)
            {
                  int next=a[now].link[j];
                  if(map[now][next] && d[now]+1<d[next])
                  {
                        d[next]=d[now]+1;
                        q[++tot]=next;
                        if(tot==M)   return true;
                  }
            }
      }
      return false;
}
int DINIC(int now,int flow)//flow         
{
      int new1;
      if(flow==0)  return 0;//       
      if(now==M)   return flow;//        
      for(int i=0;i<a[now].link.size();i++)
      {
            int next=a[now].link[i];
            if(d[now]+1==d[next] && (new1=DINIC(next,min(flow,map[now][next]))))
            {
                  map[now][next]-=new1;
                  map[next][now]+=new1;//               
                  return new1;
            }
      }
      return 0;
}
int main()
{
      freopen("ditch.in","r",stdin);
	  freopen("ditch.out","w",stdout); 
	  memset(map,0,sizeof(map));
	  scanf("%d%d",&N,&M);
	  for(int i=1;i<=N;i++)
	  {
            int A,B,C;
            scanf("%d%d%d",&A,&B,&C);
            map[A][B]+=C;
            a[A].link.push_back(B);
            a[B].link.push_back(A);
      }
      
      while(build())
      {
            while(use=DINIC(1,IMAX))
            {
                  ans+=use;
            }
      }
      printf("%d
",ans);
	  //system("pause");
      return 0;
}

 
転載して出典を明記する:http://blog.csdn.net/u011400953