P4014 分配问题

题目描述

有 nnn 件工作要分配给 nnn 个人做。第 iii 个人做第 jjj 件工作产生的效益为 cijc_{ij}cij​ 。试设计一个将 nnn 件工作分配给 nnn 个人做的分配方案，使产生的总效益最大。

输入格式

文件的第 111 行有 111 个正整数 nnn，表示有 nnn 件工作要分配给 nnn 个人做。

接下来的 nnn 行中，每行有 nnn 个整数 cijc_{ij}cij​​​，表示第 iii 个人做第 jjj 件工作产生的效益为 cijc_{ij}cij​。

输出格式

两行分别输出最小总效益和最大总效益。

输入输出样例

输入 #1

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

输出 #1

5
14

说明/提示

1≤n≤1001 \leq n \leq 1001≤n≤100

一个人只能修一个工件

思路

人和任务可以划分为二分图，建图+最大流最小费用和最大流最大费用

代码

#include<bits/stdc++.h>
#define N 10007
#define M 200007
#define inf 1<<29
using namespace std;
struct node{
    int y,z,next,p;
}e[M*2];
int a[107][107],head[N*4];
int n,s,t,tot=1,maxflow,ans;
void add(int x,int y,int z,int p){
    e[++tot].y=y;e[tot].z=z;e[tot].p=p;e[tot].next=head[x];head[x]=tot;
    e[++tot].y=x;e[tot].z=0;e[tot].p=-p;e[tot].next=head[y];head[y]=tot;
}
int incf[N],v[N],pre[N],d[N];
bool spfa(){
    queue<int> q;
    memset(d,0x3f,sizeof(d));
    memset(v,0,sizeof(v));
    q.push(s);d[s]=0;v[s]=1;
    incf[s]=inf;
    while(!q.empty()){
        int x=q.front();v[x]=0;q.pop();
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].y,z=e[i].z;
            if(!z) continue;
            if(d[y]>d[x]+e[i].p){
                d[y]=d[x]+e[i].p;
                incf[y]=min(incf[x],z);
                pre[y]=i;
                if(!v[y]) q.push(y),v[y]=1;
            }
        }
    }
    if(d[t]==0x3f3f3f3f) return false;
    return true;
}
void update(){
    int x=t;
    while(x!=s){
        int i=pre[x];
        e[i].z-=incf[t];
        e[i^1].z+=incf[t];
        x=e[i^1].y;
    }
    ans+=d[t]*incf[t];
}
int main()
{
    cin>>n;s=0;t=n*2+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++)
        add(s,i,1,0),add(i+n,t,1,0);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            add(i,j+n,1,a[i][j]);
    while(spfa()) update();
    cout<<ans<<endl;
    memset(head,0,sizeof(head));tot=1;maxflow=ans=0;
    for(int i=1;i<=n;i++)
        add(s,i,1,0),add(i+n,t,1,0);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            add(i,j+n,1,-a[i][j]);
    while(spfa()) update();
        cout<<-ans<<endl;
    return 0;
}