首页 > 代码库 > 最小费用最大流

最小费用最大流

2024-08-07 00:33:17   221人阅读

我最近学习了最小费用最大流；

我还是简略谈谈最小费用最大流吧

什么是最小费用最大流?

我们可以把最小费用看做是最短路；

简单吧！！！！

也就是一条边有两个权值；

一个为边权，另一个为流值；

什么是最大流？

当我们求出了最小费用时；

实质上求出了最短路；

而此时最大流为最短路上的每一条边的流值的最小值；

此时最小费用最大流为最短路的长度*最大流；

怎么求最小费用？

很简单！！！！！

我们就是求单源最短路径；

我们可以写spfa Dijkstra  Bellman-Ford floyd（这个作死）

我们每次求完最小费用最大流时；

我们应把最短路上所有边反向；

使反向的边的边权为它所对应的正向边权的相反数；

而正向边的流值应减去最大流；反向边的流值应加上最大流（流值最开始为0）；

哦！别忘了将正向边的流值为0的边的权值该为无穷大；（防止走重复的最短路）；

我们一直这样操作，直到起点连不到终点，在退出，每次的最小费用最大流加起来则为总的最小费用最大流；


给作参考：

#include<stdio.h>

#include<stdlib.h>
#define max1 1000000000
int a[1000][1000],f[1000][1000];
int d[1000];//d表示某特定边距离
int p[1000],h[1000];//p表示永久边距离
int i,j,sum=0,ans=0;
int m;//m代表边数
int n,g;//n代表点数
int dfs(int k,int h1)
{
    int j;
if(f[h[k]][k]<h1 && f[h[k]][k]!=0)h1=f[h[k]][k];
a[k][h[k]]=-a[h[k]][k];
    //printf("%d ",h[k]);
    if(h[k]==1)return h1;
    j=dfs(h[k],h1);
    return j;
}
int cherk(int t,int k)
{
    f[h[t]][t]-=k;f[t][h[t]]+=k;
    if(f[h[t]][t]==0)a[h[t]][t]=max1;
if(h[t]==1)return 0;
    cherk(h[t],k);
    return 0;
}
int main()
{
   //freopen("dj.in","r",stdin);
   //freopen("dj.out","w",stdout);
   scanf("%d%d",&n,&m);
   int min1,x,y,z,w,k,o=0;
   for(i=1;i<=m;i++)
   {
    scanf("%d%d%d%d",&x,&y,&z,&w);//z是流,w是费用;
    a[x][y]=w;f[x][y]=z;
//a[y][x]=-w;
f[y][x]=0;
   }
   for(o=1;;o++)
   {
   k=0;
   for(i=1;i<=n;i++)
    d[i]=max1;
   d[1]=0;
   for(i=1;i<=n;i++)
    {h[i]=0;p[i]=0;}
   for(i=1;i<=n;i++)
   {
    min1=max1;
    for(j=1;j<=n;j++)
    if(!p[j]&&d[j]<min1)
{
     min1=d[j];
     k=j;
    }
    p[k]=1;
    for(j=1;j<=n;j++)
     if(a[k][j]!=0&&!p[j]&&d[j]>d[k]+a[k][j])
      {d[j]=d[k]+a[k][j];h[j]=k;}
   }
   if(d[n]>=max1)
    break;
   k=548566;
   //for(i=1;i<=n;i++)
   // printf("%d ",h[i]);
   //printf("%d",&h[i]); 
   k=dfs(n,k);
   cherk(n,k);
   sum+=k*d[n];ans+=k;
   //printf("%d %d\n",k,d[n]);
   }
   printf("%d %d",ans,sum);
   //for(i=1;i<=n;i++)
   // printf("%d ",d[i]);
   //fclose(stdin);
   //fclose(stdout);
   //while(1);
   return 0;
}

最小费用最大流


联系
我们