最小费用最大流.txt

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

#include <stdio.h>   //用bellman_ford找增广路，改变时增加回边，费用为负
#include <math.h>    //这个算法我同陈诗毅师兄个代码对过，相同输入答案相同，不过系pku过唔到～～，希望有人指正一下
#include <string.h> 
#include <algorithm>
#include <queue>
#define N 1005
#define M 999999
using namespace std;

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

struct sea
{
 int num,pla,pre;
};

int s,t;
int cost=0,flow=0;
sea m[N]={0};

bool findpath()
{
 int i,j,use,check;
 int d,e;
 int dist[N]={0};
 sea mid;
 
 queue<int> que;
 que.push(s);
 check=s;
 memset(m,0,sizeof(m));
 
 for(i=s;i<=t;i++) dist[i]=M;
 dist[s]=0;

 while(1)
 {
  for(i=1;i<point[check].num;i++)
  {
   d=dist[check]+point[check].cost[i];
   e=abs(point[check].flow[i]);
   if(d<dist[(point[check].road[i])]&&e)
   {
    mid.num=check;                              //标号
    mid.pla=i;
    dist[point[check].road[i]]=d;
    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].flow[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].flow[m[a].pla]-=Min;
  cost+=point[m[a].num].cost[m[a].pla]*Min;
  if(!point[a].turn[b]) 
  {
   point[a].flow[point[a].num]+=Min;
   point[a].cost[point[a].num]=-point[b].cost[m[a].pla];
   point[a].road[point[a].num]=b;
   point[a].num++;
   point[a].turn[b]=point[a].num-1;
  }
  else {point[a].flow[point[a].turn[b]]+=Min;}
 }
 return Min;
}

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

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