[toc]

题目链接：Luogu P4014/LibreOJ 6012/PowerOJ 1753。

网络流 24 题，费用流的简单应用。

题目

题目描述

有 $n$ 件工作要分配给 $n$ 个人做，一个人只能修一个工件。第 $i$ 个人做第 $j$ 件工作产生的效益为 $c_{i,j}$。试设计一个将 $n$ 件工作分配给 $n$ 个人做的分配方案，使产生的总效益最大（小）。

数据范围

$$1\leq n\leq 100$$

时空限制

$$\text{Luogu}:1\text{s}/250\text{MiB}$$

$$\text{LibreOJ}:1\text{s}/256\text{MiB}$$

$$\text{PowerOJ}:1\text{s}/64\text{MiB}$$

题解

思路

考虑题目要求。

1. $n$ 件工作要分配给 $n$ 个人做。
   二分图完美匹配（最大流）。
2. 一个人只能修一个工件。
   源点到代表每个人的点的边容量为 $1$。
   代表每个工件的点到汇点的边容量为 $1$。
3. 效益为 $c_{i,j}$，使效益最大（小）化。
   最大（小）费用最大流。

于是这道 网络流 24 题 之一就这么结束了。

代码

渐进时间复杂度为$\Theta(n^2+\alpha(n^2,n^2))$，其中 $\alpha(n^2,n^2)$ 表示费用流的时间复杂度。

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define INF 0X3F3F3F3F //定义正无穷
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){ //读入优化
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=100+5;

inline void Read(void);
inline void Work(void);

int main(void){
    Read();
    Work();
    return 0;
}

int n,s,t;
int cnt=1,head[MAXN<<1],to[(MAXN*MAXN+MAXN*2)<<1],w[(MAXN*MAXN+MAXN*2)<<1],p[(MAXN*MAXN+MAXN*2)<<1],Next[(MAXN*MAXN+MAXN*2)<<1]; //邻接表存图

inline void Add_Edge(reg int u,reg int v,reg int len,reg int val){
    Next[++cnt]=head[u];
    to[cnt]=v;
    w[cnt]=len;
    p[cnt]=val;
    head[u]=cnt;
    return;
}

inline void Add_Tube(reg int u,reg int v,reg int len,reg int val){
    Add_Edge(u,v,len,val);
    Add_Edge(v,u,0,-val);
    return;
}

inline void Read(void){
    n=read();
    s=0,t=2*n+1; //源点和汇点
    for(reg int i=1;i<=n;++i){
        for(reg int j=1;j<=n;++j){
            static int c; //读入 c[][]，但无需保存，所以只定义一个变量
            c=read();
            Add_Tube(i,j+n,1,c);
        }
    }
    for(reg int i=1;i<=n;++i)
        Add_Tube(s,i,1,0); //将人与源点连接
    for(reg int i=1;i<=n;++i)
        Add_Tube(i+n,t,1,0); //将工件与汇点连接
    return;
}

bool inque[MAXN<<1];
int dis[MAXN<<1];
queue<int> Q;

inline bool SPFA_Min(int s,reg int t){ //SPFA 求最短路
    memset(inque,false,sizeof(inque));
    memset(dis,0X3F,sizeof(dis));
    while(!Q.empty())Q.pop();
    inque[s]=true,dis[s]=0,Q.push(s);
    while(!Q.empty()){
        reg int ID=Q.front();
        Q.pop();
        inque[ID]=false;
        for(reg int i=head[ID];i;i=Next[i]){
            if(dis[to[i]]>dis[ID]+p[i]&&w[i]>0){
                dis[to[i]]=dis[ID]+p[i];
                if(!inque[to[i]]){
                    inque[to[i]]=true;
                    Q.push(to[i]);
                }
            }
        }
    }
    return dis[t]!=INF;
}

inline bool SPFA_Max(int s,reg int t){ //SPFA 求最长路
    memset(inque,false,sizeof(inque));
    fill(dis,dis+t+1,-INF);
    while(!Q.empty())Q.pop();
    inque[s]=true,dis[s]=0,Q.push(s);
    while(!Q.empty()){
        reg int ID=Q.front();
        Q.pop();
        inque[ID]=false;
        for(reg int i=head[ID];i;i=Next[i]){
            if(dis[to[i]]<dis[ID]+p[i]&&w[i]>0){
                dis[to[i]]=dis[ID]+p[i];
                if(!inque[to[i]]){
                    inque[to[i]]=true;
                    Q.push(to[i]);
                }
            }
        }
    }
    return dis[t]!=-INF;
}

bool vis[MAXN<<1];
int cur[MAXN<<1]; //当前弧优化
int Cost; //保存费用

inline int DFS(reg int ID,reg int t,reg int lim){ //费用流求增广路
    if(ID==t){
        Cost+=dis[t]*lim;
        return lim;
    }
    vis[ID]=true;
    reg int flow=0;
    for(reg int &i=cur[ID];i;i=Next[i]) //当前弧优化
        if(dis[to[i]]==dis[ID]+p[i]&&w[i]>0&&!vis[to[i]]){
            reg int f=DFS(to[i],t,min(lim-flow,w[i]));
            if(f){
                flow+=f;
                w[i]-=f;
                w[i^1]+=f;
                if(flow==lim)
                    break;
            }
        }
    vis[ID]=false;
    return flow;
}

inline int Dinic_Min(reg int s,reg int t){ //求最小费用最大流
    Cost=0;
    reg int res=0;
    while(SPFA_Min(s,t)){
        memcpy(cur,head,sizeof(head));
        res+=DFS(s,t,INF);
    }
    return res;
}

inline int Dinic_Max(reg int s,reg int t){ //求最大费用最大流
    Cost=0;
    reg int res=0;
    while(SPFA_Max(s,t)){
        memcpy(cur,head,sizeof(head));
        res+=DFS(s,t,INF);
    }
    return res;
}

inline void Work(void){
    reg int ans1,ans2; //定义答案
    Dinic_Min(s,t); //求最小费用最大流
    ans1=Cost;
    for(reg int i=2;i<=cnt;++i)
        w[i]=1^(i&1); //重置边权，
    Dinic_Max(s,t); //求最大费用最大流
    ans2=Cost;
    printf("%d\n%d\n",ans1,ans2); //输出答案
    return;
}