精华内容
下载资源
问答
  • 最小费用最大流

    2017-02-09 16:59:26
    学习了一下最小费用最大流,发现其实就是在原来每条边的定义加上一个单位流量的费用,so寻找增广路时采用贪心的思想,每次找费用和最小的路径即可。 废话少说,上代码://POJ2135 #include #include #include #...

    学习了一下最小费用最大流,发现其实就是在原来每条边的定义加上一个单位流量的费用,so寻找增广路时采用贪心的思想,每次找费用和最小的路径即可。
    废话少说,上代码:

    //POJ2135
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    #define maxn 1005
    #define maxm 10005
    #define INF 0x7ffffff//被fff坑死QAQ~~~ 
    using namespace std;
    int flow,u,v,cost,n,m,id[maxn],head[maxn],q,s,t,x,y,num,d[maxn],inq[maxn],a[maxn],pre[maxn];
    
    struct xx{
        int v,next,cap,cost;
    }b[maxm*4];
    
    void add(int u,int v ,int q,int cost)
    {
        b[num]=(xx){v,head[u],q,cost};
        head[u]=num++;
        b[num]=(xx){u,head[v],0,-cost};
        head[v]=num++;
    }
    
    int Bellford(int s,int t,int& flow,int& cost)
    {
        //memset(d,INF,sizeof(d));
        for (int i=0;i<=t;i++) d[i]=INF;
        memset(inq,0,sizeof(inq));
        d[s]=0;inq[s]=1;pre[s]=-1;a[s]=INF;id[s]=-1;
        queue <int> q;
        q.push(s);
        while(!q.empty())
        {
            int u=q.front();q.pop();
            inq[u]=0;
            for (int i=head[u];i!=-1;i=b[i].next)
            {
                int v=b[i].v;
                if (d[u]+b[i].cost<d[v]&&b[i].cap)
                {
                    d[v]=d[u]+b[i].cost;
                    pre[v]=u;
                    id[v]=i;
                    a[v]=min(a[u],b[i].cap);
                    if (!inq[v]) inq[v]=1,q.push(v);
                }
            }
        }
        if (d[t]==INF) return 0;
        flow+=a[t];
        cost+=d[t]*a[t];
         u=t;
        while (u!=s)
        {
            b[id[u]].cap-=a[t];
            b[id[u]^1].cap+=a[t];
            u=pre[u];
        }
        return true;
    }
    
    int Mincost()
    {
        flow=0,cost=0;
        while (Bellford(s,t,flow,cost));
        return cost;
    }
    
    int main()
    {
        scanf("%d%d",&n,&m);
        num=0;s=0;t=n+1;
        memset(head,-1,sizeof(head));
        for (int i=1;i<=m;i++)
             scanf("%d%d%d",&x,&y,&q),add(x,y,1,q),add(y,x,1,q);
        add(s,1,2,0);add(n,t,2,0);
        printf("%d",Mincost());
        return 0;
    }
    展开全文
  • 最小费用最大流问题matlab实现
  • 最小费用最大流模板

    2012-11-26 12:43:30
    最小费用最大流模板
  • 可以解决非完备匹配问题中的最大权匹配和最小权匹配,分别对应着最大费用最大流和最小费用最大流 模板: 最大费用最大流: const int N=1e5+100;//点 const int M=1e5+100;//边 struct Edge { int to,w,cost,...

    主要是思维建边,建有向边,然后跑模板就行了

    可以解决KM算法所能解决的问题(完全取代)

    可以解决非完备匹配问题中的最大权匹配和最小权匹配,分别对应着最大费用最大流和最小费用最大流

    模板:

    最大费用最大流:

    const int N=1e5+100;//点
    
    const int M=1e5+100;//边
    
    struct Edge
    {
    	int to,w,cost,next;
    }edge[M];
    
    int head[N],cnt;
    
    void addedge(int u,int v,int w,int cost)
    {
    	edge[cnt].to=v;
    	edge[cnt].w=w;
    	edge[cnt].cost=cost;
    	edge[cnt].next=head[u];
    	head[u]=cnt++;
    	edge[cnt].to=u;
    	edge[cnt].w=0;
    	edge[cnt].cost=-cost;
    	edge[cnt].next=head[v];
    	head[v]=cnt++;
    }
    
    int d[N],incf[N],pre[N];
    
    bool vis[N];
    
    bool spfa(int s,int t)
    {
    	memset(d,0xcf,sizeof(d));
    	memset(vis,false,sizeof(vis));
        memset(pre,-1,sizeof(pre));
    	queue<int>q;
    	q.push(s);
    	vis[s]=true;
    	incf[s]=inf;
    	d[s]=0;
    	while(!q.empty())
    	{
    		int u=q.front();
    		q.pop();
    		vis[u]=false;
    		for(int i=head[u];i!=-1;i=edge[i].next)
    		{
    			int v=edge[i].to;
    			int w=edge[i].w;
    			int cost=edge[i].cost;
    			if(!w)
    				continue;
    			if(d[v]<d[u]+cost)
    			{
    				d[v]=d[u]+cost;
    				pre[v]=i;
    				incf[v]=min(incf[u],w);
    				if(!vis[v])
    				{
    					vis[v]=true;
    					q.push(v);
    				}
    			}
    		}
    	}
    	return pre[t]!=-1;
    }
    
    int update(int s,int t)
    {
    	int x=t;
    	while(x!=s)
    	{
    		int i=pre[x];
    		edge[i].w-=incf[t];
    		edge[i^1].w+=incf[t];
    		x=edge[i^1].to;
    	}
    	return d[t]*incf[t];
    }
    
    void init()
    {
    	memset(head,-1,sizeof(head));
    	cnt=0;
    }
    
    int solve(int st,int ed)
    {
    	int ans=0;
    	while(spfa(st,ed))
    		ans+=update(st,ed);
    	return ans;
    }

    最小费用最大流:

    const int N=1e5+100;//点
    
    const int M=1e5+100;//边
    
    struct Edge
    {
    	int to,w,cost,next;
    }edge[M];
    
    int head[N],cnt;
    
    void addedge(int u,int v,int w,int cost)
    {
    	edge[cnt].to=v;
    	edge[cnt].w=w;
    	edge[cnt].cost=cost;
    	edge[cnt].next=head[u];
    	head[u]=cnt++;
    	edge[cnt].to=u;
    	edge[cnt].w=0;
    	edge[cnt].cost=-cost;
    	edge[cnt].next=head[v];
    	head[v]=cnt++;
    }
    
    int d[N],incf[N],pre[N];
    
    bool vis[N];
    
    bool spfa(int s,int t)
    {
    	memset(d,inf,sizeof(d));
    	memset(vis,false,sizeof(vis));
        memset(pre,-1,sizeof(pre));
    	queue<int>q;
    	q.push(s);
    	vis[s]=true;
    	incf[s]=inf;
    	d[s]=0;
    	while(!q.empty())
    	{
    		int u=q.front();
    		q.pop();
    		vis[u]=false;
    		for(int i=head[u];i!=-1;i=edge[i].next)
    		{
    			int v=edge[i].to;
    			int w=edge[i].w;
    			int cost=edge[i].cost;
    			if(!w)
    				continue;
    			if(d[v]>d[u]+cost)
    			{
    				d[v]=d[u]+cost;
    				pre[v]=i;
    				incf[v]=min(incf[u],w);
    				if(!vis[v])
    				{
    					vis[v]=true;
    					q.push(v);
    				}
    			}
    		}
    	}
    	return pre[t]!=-1;
    }
    
    int update(int s,int t)
    {
    	int x=t;
    	while(x!=s)
    	{
    		int i=pre[x];
    		edge[i].w-=incf[t];
    		edge[i^1].w+=incf[t];
    		x=edge[i^1].to;
    	}
    	return d[t]*incf[t];
    }
    
    void init()
    {
    	memset(head,-1,sizeof(head));
    	cnt=0;
    }
    
    int solve(int st,int ed)
    {
    	int ans=0;
    	while(spfa(st,ed))
    		ans+=update(st,ed);
    	return ans;
    }

     

    展开全文
  • 最小费用最大流C++算法,有最小费用算法,最大流算法,最短路算法,C++代码。
  • 实验三使用matlab求解最小费用最大流算问题 精品文档 精品文档 收集于网络如有侵权请联系管理员删除 收集于网络如有侵权请联系管理员删除 精品文档 收集于网络如有侵权请联系管理员删除 北京联合大学 实验报告 项目...
  • 实 验 三 使 用 ma t l a b 求 解 最 小 费 用 最 大 流 算 问题 精品文档 北京联合大学 实验报告 项目...5 月 6 日 收集于网络如有侵权请联系管理员删除 精品文档 实验三使用 matlab 求解最小费用最大流算问题 一实
  • 因为有多种商品,所以可以简化构图过程,每一次求一种商品的最小费用最大流,然后最终将所有商品的最小费用最大流的总和加起来就可以了,注意条件在代码中解释。 注意: 对于源点到供应商这一段不能...

    题目链接:https://cn.vjudge.net/contest/68128#problem/E

    具体思路:图的建立方式, 超级源点 - >  供应商 - > 顾客 - > 超级汇点。

    因为有多种商品,所以可以简化构图过程,每一次求一种商品的最小费用最大流,然后最终将所有商品的最小费用最大流的总和加起来就可以了,注意条件在代码中解释。

    注意: 对于源点到供应商这一段不能设置成inf,具体例子如下所示。

    s -  >s1,同时s1 - >s2,s1 - > s3。这样的话,就相当于有两条路从s出发,本来s到s1的流量总和为5,但是如果把流量设置成inf,

    那么如果本来s1 - >s2,s1 - > s3这两条路的和是超过5的,也就是说按照原来的建图方式,初始从s-> s1 的流量是不够用的,如果改成inf的话,流量就够用,那么就改变题意了。

    AC代码:

    #include<iostream>
    #include<string>
    #include<cstring>
    #include<iomanip>
    #include<cmath>
    #include<algorithm>
    #include<map>
    #include<queue>
    #include<stack>
    #include<vector>
    #include<stdio.h>
    using namespace std;
    # define inf 0x3f3f3f3f
    # define maxn 150+100
    # define ll long long
    int need[maxn][maxn];
    int store[maxn][maxn];
    int Map[maxn][maxn][maxn];// i - > numofstore ,j- > huowu ,k - > keeper
    int sum1[maxn],sum2[maxn];
    int head[maxn];
    int dis[maxn],prev[maxn],pree[maxn];
    int vis[maxn];
    int num;
    struct Edge
    {
        int to;
        int cost;
        int w;
        int nex;
    } edge[maxn];
    void addage(int fr,int to,int w,int cost)
    {
        edge[num].to=to;
        edge[num].w=w;
        edge[num].cost=cost;
        edge[num].nex=head[fr];
        head[fr]=num++;
        edge[num].to=fr;
        edge[num].w=0;
        edge[num].cost=-cost;
        edge[num].nex=head[to];
        head[to]=num++;
    }
    bool spfa(int st,int ed)
    {
        memset(vis,0,sizeof(vis));
        memset(pree,-1,sizeof(pree));
        memset(dis,inf,sizeof(dis));
        dis[st]=0;
        vis[st]=1;
        queue<int>q;
        q.push(st);
        while(!q.empty())
        {
            int top=q.front();
            q.pop();
            vis[top]=0;
            for(int i=head[top]; i!=-1; i=edge[i].nex)
            {
                int temp=edge[i].to;
                if(edge[i].w>0&&dis[temp]>dis[top]+edge[i].cost)
                {
                    dis[temp]=dis[top]+edge[i].cost;
                    pree[temp]=top;
                    prev[temp]=i;
                    if(vis[temp]==0)
                    {
                        vis[temp]=1;
                        q.push(temp);
                    }
                }
            }
        }
        return pree[ed]!=-1;
    }
    int mincostflow(int st,int ed)
    {
        int ans=0;
        while(spfa(st,ed))
        {
            int minn=inf;
            for(int i=ed; i!=st; i=pree[i])
            {
                minn=min(minn,edge[prev[i]].w);
            }
            ans+=minn*dis[ed];//dis代表一个单位的花费,minn代表流量。
            for(int i=ed; i!=st; i=pree[i])
            {
                edge[prev[i]].w-=minn;
                edge[prev[i]^1].w+=minn;
            }
        }
        return ans;
    }
    int main()
    {
        int n,m,k;
        while(~scanf("%d%d%d",&n,&m,&k)&&(n+m+k))
        {
            int flag=0;
            memset(need,0,sizeof(need));
            memset(sum1,0,sizeof(sum1));
            memset(sum2,0,sizeof(sum2));
            memset(Map,0,sizeof(Map));
            for(int i=1; i<=n; i++)
            {
                for(int j=1; j<=k; j++)
                {
                    scanf("%d",&need[i][j]);
                    sum1[j]+=need[i][j];
                }
            }// xu qiu liang
            for(int i=1; i<=m; i++)
            {
                for(int j=1; j<=k; j++)
                {
                    scanf("%d",&store[i][j]);
                    sum2[j]+=store[i][j];
                }
            }
            for(int i=1; i<=k; i++)
            {
                if(sum1[i]>sum2[i])//判断能否满足构图的条件
                {
                    flag=1;
                }
            }
            for(int h=1; h<=k; h++)
            {
                for(int i=1; i<=n; i++)
                {
                    for(int j=1; j<=m; j++)
                    {
                        scanf("%d",&Map[h][j][i]);// 第j种货物从j仓库到达第i个买家的花费
                    }
                }
            }
            if(flag==1)printf("-1\n");
            else
            {
                int ans=0;
                for(int h=1; h<=k; h++)
                {
                    memset(head,-1,sizeof(head));
                    num=0;
                    for(int i=1; i<=m; i++)
                    {
                        addage(0,i,store[i][h],0);//注意这里的流量设置,不能设置成inf。
                    }
                    for(int i=1; i<=m; i++)
                    {
                        for(int j=1; j<=n; j++)
                        {
                            addage(i,j+m,inf,Map[h][i][j]);//这里的流量即可以设置成inf,也可以设置成存货。
                        }
                    }
                    for(int i=1; i<=n; i++)
                    {
                        addage(m+i,n+m+1,need[i][h],0);//这里设置成需求量。
                    }
                    ans+=mincostflow(0,n+m+1);
                }
                printf("%d\n",ans);
            }
        }
        return 0;
    }
    

     

    展开全文
  • 最小费用最大流问题

    千次阅读 2019-07-04 11:11:13
    最小费用最大流问题 解决如下最小费用最大流问题。 查了很多资源发现用MATLAB操作的好用的不多,所以综合了一下很多资源,给出了自己的理解。 基本思路为:把各条弧上单位流量的费用当做距离,用Floyd算法求最...

    最小费用最大流问题
    解决如下最小费用最大流问题。
    以前的资源由于matlab版本问题等已不适用。现在做出修改,适用于matlab2014a以后的版本。
    注意,数据格式按代码中的例子的格式,否则需要修改代码。
    查了很多资源发现用MATLAB操作的好用的不多,所以综合了一下很多资源,给出了自己的理解。
    网络
    基本思路为:把各条弧上单位流量的费用当做距离,用Floyd算法求最短路,确定一条自V1至Vn的最短路;再将这条最短路作为初始路径,用求解最大流问题的方法将其上的流量增至最大可能值;而这条最短路上的流量增加后,其上各条弧的单位流量的费用要重新确定,如此多次迭代,最终得到最小费用最大流。
    代码由GreenSim原创(源代码下载积分46),在其基础上加调试。读者根据自己需要设置流量矩阵和费用矩阵。
    代码

    展开全文
  • 最小费用最大流 理解

    2017-08-02 18:16:41
    最小费用最大流
  • 基于matlab2016的最小费用最大流问题求解,内含增广链路函数[path,value] = AugmentingPath(G,s,t)和一个demo函数。 寻找增广链路时,使用了matlab自带的最短路径shortestpath函数,demo中使用了matlab自带的...
  • 网络流-最小费用最大流总结。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 26,494
精华内容 10,597
关键字:

最小费用最大流