首页 > 题解 > 网络流24题之十八 分配问题

网络流24题之十八 分配问题

填坑

地址:cv1915

题目描述 Description

有n件工作要分配给n个人做。第i 个人做第j 件工作产生的效益为ij c 。试设计一个将n件工作分配给n个人做的分配方案,使产生的总效益最大。
«编程任务:
对于给定的n件工作和n个人,计算最优分配方案和最差分配方案。

输入描述 Input Description

第1 行有1 个正整数n,表示有n件工作要分配给n 个人做。接下来的n 行中,每行有n 个整数 cij ,1≤i≤n,1≤j≤n,表示第i 个人做第j件工作产生的效益为cij

输出描述 Output Description

将计算出的最小总效益和最大总效益输出

样例输入 Sample Input

5
2 2 2 1 2
2 3 1 2 4
2 0 1 1 1
2 3 4 3 3
3 2 1 2 1

样例输出 Sample Output

5
14

模型

二分图最佳匹配问题,可以费用流解决(或KM算法)。

实现

把所有人看做二分图中顶点Xi,所有工作看做二分图中顶点Yi,建立附加源S汇T。

1、从S向每个Xi连一条容量为1,费用为0的有向边。
2、从每个Yi向T连一条容量为1,费用为0的有向边。
3、从每个Xi向每个Yj连接一条容量为无穷大,费用为Cij的有向边。

求最小费用最大流,最小费用流值就是最少运费,求最大费用最大流,最大费用流值就是最多运费。

分析

二分图最佳匹配建模方法为费用流模型。

代码

#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
#include <string>
#include <cstring>
#include <iostream>
#define M 50000
#define N 500
#define INF 0x33333333
#define min(x,y) ((x<y)?(x):(y))
using namespace std;
typedef pair<int,int> Pair;
map <string,int>ma;
struct node{int from,to,next,flow,cost;}e[M];
int tot=-1,st[M];
int n,m,x,y,z;
int pe[N],pv[N],dis[N],vis[N];
void add(int x,int y,int z,int zz){
    e[++tot].to=y;
    e[tot].from=x;
    e[tot].flow=z;
    e[tot].cost=zz;
    e[tot].next=st[x];
    st[x]=tot;
}
void add_edge(int x,int y,int z,int zz){add(x,y,z,zz),add(y,x,0,-zz);}
queue<int>que;
bool maxspfa(int S,int T)
{
    for (int i=S;i<=T;i++)
        dis[i]=-INF;
    memset(vis,0,sizeof vis);
    que.push(S),vis[S]=1,dis[S]=0;
    while(!que.empty())
    {
        int now=que.front();que.pop();vis[now]=0;
        for (int i=st[now];~i;i=e[i].next)
            if (e[i].flow>0 && dis[e[i].to]<dis[now]+e[i].cost)
            {
                dis[e[i].to]=dis[now]+e[i].cost;
                pe[e[i].to]=i,pv[e[i].to]=now;
                if (!vis[e[i].to])
                    vis[e[i].to]=1,que.push(e[i].to);
            }
    }
    return dis[T]!=-INF;
}
Pair mfmaxc(int S,int T)
{
    int COST=0,FLOW=0,flow;
    while(maxspfa(S,T))
    {
        flow=0x3f3f3f3f;
        for (int i=T;i!=S;i=pv[i])
            flow=min(flow,e[pe[i]].flow);
        COST+=flow*dis[T];
        FLOW+=flow;
        for (int i=T;i!=S;i=pv[i])
            e[pe[i]].flow-=flow,e[pe[i]^1].flow+=flow;
    }
    return make_pair(FLOW,COST);
}
bool minspfa(int S,int T)
{
    memset(dis,0x33,sizeof dis);
    memset(vis,0,sizeof vis);
    que.push(S),vis[S]=1,dis[S]=0;
    while(!que.empty())
    {
        int now=que.front();que.pop();vis[now]=0;
        for (int i=st[now];~i;i=e[i].next)
            if (e[i].flow>0 && dis[e[i].to]>dis[now]+e[i].cost)
            {
                dis[e[i].to]=dis[now]+e[i].cost;
                pe[e[i].to]=i,pv[e[i].to]=now;
                if (!vis[e[i].to])
                    vis[e[i].to]=1,que.push(e[i].to);
            }
    }
    return dis[T]<INF;
}
Pair mfminc(int S,int T)
{
    int COST=0,FLOW=0,flow;
    while(minspfa(S,T))
    {
        flow=INF;
        for (int i=T;i!=S;i=pv[i])
            flow=min(flow,e[pe[i]].flow);
        COST+=flow*dis[T];
        FLOW+=flow;
        for (int i=T;i!=S;i=pv[i])
            e[pe[i]].flow-=flow,e[pe[i]^1].flow+=flow;
    }
    return make_pair(FLOW,COST);
}
main()
{
    memset(st,-1,sizeof st);
    memset(e,-1,sizeof e);
    scanf("%d",&n);
    int S=0,T=n+n+1,cost[N][N];
    for (int i=1;i<=n;i++)
        add_edge(S,i,1,0);
    for (int i=1;i<=n;i++)
        add_edge(i+n,T,1,0);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            scanf("%d",&cost[i][j]),add_edge(i,j+n,INF,cost[i][j]);
    Pair ans=mfminc(S,T);
    printf("%d\n",ans.second);
    memset(st,-1,sizeof st);
    memset(e,-1,sizeof e);
    for (int i=1;i<=n;i++)
        add_edge(S,i,1,0);
    for (int i=1;i<=n;i++)
        add_edge(i+n,T,1,0);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            add_edge(i,j+n,INF,cost[i][j]);
    ans=mfmaxc(S,T);
    printf("%d",ans.second);
}