网络最大流.txt

图论常用算法的C语言程序,对于图论的一些应用有很大的指导作用!

#include <stdio.h>           //邻接表存图，用标号法找增广路
#include <string.h> 
#include <algorithm>
#include <queue>
#define N 1005
using namespace std;

struct points
{
 int c[N];
 int road[N];
 int turn[N];
 int num;
}point[N]={0};

struct sea
{
 int num,pla;
 bool use;
};

int s,t;
bool real=false;;
sea m[N]={0};

bool findpath()
{
 int i,j,use,check;
 sea mid;
 
 queue<int> que;
 que.push(s);
 check=s;
 memset(m,0,sizeof(m));
 
 while(1)
 {
  for(i=0;i<point[check].num;i++)
  {
   if(m[point[check].road[i]].use||!point[check].c[i]) continue;

   mid.num=check;                               //标号
   mid.pla=i;
   mid.use=true;
   m[point[check].road[i]]=mid;
   que.push(point[check].road[i]);              //入队
  }
  if(que.empty()) return false;
  check=que.front();
  que.pop();
  if(check==t) break;
 }
 return true;
}

int addpath()
{
 int road[N]={0};
 int i,mid,check,Min;
 int a,b,c;
 mid=0;check=t;Min=1<<30;
 while(1)
 {
  road[mid++]=check;
  check=m[check].num;
  if(check==s) break;
 }
 road[mid++]=s;
 for(i=0;i<mid-1;i++)
 {
  a=road[i];
  c=point[m[a].num].c[m[a].pla];
  if(c<Min) Min=c;
 }
 for(i=0;i<mid-1;i++)
 {
  a=road[i];b=m[a].num;
  point[m[a].num].c[m[a].pla]-=Min;
  if(!point[a].turn[b]) 
  {
   point[a].c[point[a].num]+=Min;
   point[a].road[point[a].num]=b;
   point[a].num++;
   point[a].turn[b]=point[a].num-1;
  }
  else
  {
   point[a].c[point[a].turn[b]]+=Min;
  }
 }
 return Min;
}

void maxflow()
{
 int flow=0;
 while(findpath())
 {
  flow+=addpath();
 }
 printf("%d\n",flow);
}

int main()
{
 int n,k,a,b,c,i;
 scanf("%d %d",&n,&k);
 for(i=1;i<=n;i++) point[i].num++;
 while(k--)
 {
  scanf("%d %d %d",&a,&b,&c);
  point[a].c[point[a].num]=c;
  point[a].road[point[a].num]=b;
  point[a].num++;
 }
 scanf("%d %d",&s,&t);
 maxflow();
 scanf("%d",&a);
}