题意

图片说明

题解

最大最小费用流直接求解。

建图：
设源点s，汇点t。
对每个源点s与人i连边，边流量为1，费用为0，用来控制每个人只能做一个工作。
对于每个工作j与汇点t连边，边流量为1，费用为0，用来控制每个工作只能做一次。
对每个人i，工作j建边，边流量为1，费用为效益即权值。

直接跑最小费用流即可求得最小值。

然后将最小费用流改为最大费用流，即按最长路进行增广。
记得对边进行复原。

code

#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(int i=(l);i<(r);i++)
using namespace std;

const int maxn = 200 + 10;
const int mod = 1e9 + 7;

struct Edge{
    int to, cap, cost;
    int nxt;
}edges[maxn * maxn];

int head[maxn],tot;
int vis[maxn],pre[maxn],dis[maxn];

void addedge(int u,int v,int f,int c)
{
    edges[tot] = {v,f,c,head[u]};
    head[u] = tot++;
}

void addedges(int u,int v,int f,int c)
{
    addedge(u,v,f,c);
    addedge(v,u,0,-c);
}

bool spfa(int s,int t)
{
    memset(pre,-1,sizeof(pre));
    fill(dis,dis+maxn,inf);
    memset(vis,0,sizeof(vis));
    queue<int> q;
    vis[s] = 1;
    dis[s] = 0;
    q.push(s);
    while(q.size()){
        int hd = q.front();
        q.pop();
        vis[hd] = 0;
        for(int i = head[hd];~i;i = edges[i].nxt){
            auto &e = edges[i];
            if(e.cap > 0 && dis[e.to] > dis[hd] + e.cost){
                dis[e.to] = dis[hd] + e.cost;
                pre[e.to] = i;
                if(!vis[e.to]){
                    vis[e.to] = 1;
                    q.push(e.to);
                }
            }
        }
    }
    return ~pre[t];
}

int mcmf(int s,int t){
    int flow = 0;
    int cost = 0;
    while(spfa(s,t)){
        int mf= inf;
        for(int i = pre[t];~i;i = pre[edges[i^1].to]){
            mf = min(mf,edges[i].cap);
        }
        flow += mf;
        for(int i = pre[t];~i;i = pre[edges[i^1].to]){
            edges[i].cap -= mf;
            edges[i^1].cap += mf;
            cost += mf * edges[i].cost;
        }
    }
    return cost;
}

bool spfamx(int s,int t)    //最长路
{
    memset(pre,-1,sizeof(pre));
    fill(dis,dis+maxn,-inf);
    memset(vis,0,sizeof(vis));
    queue<int> q;
    vis[s] = 1;
    dis[s] = 0;
    q.push(s);
    while(q.size()){
        int hd = q.front();
        q.pop();
        vis[hd] = 0;
        for(int i = head[hd];~i;i = edges[i].nxt){
            auto &e = edges[i];
            if(e.cap > 0 && dis[e.to] < dis[hd] + e.cost){
                dis[e.to] = dis[hd] + e.cost;
                pre[e.to] = i;
                if(!vis[e.to]){
                    vis[e.to] = 1;
                    q.push(e.to);
                }
            }
        }
    }
    return ~pre[t];
}

int mxmf(int s,int t){
    int flow = 0;
    int cost = 0;
    while(spfamx(s,t)){
        int mf= inf;
        for(int i = pre[t];~i;i = pre[edges[i^1].to]){
            mf = min(mf,edges[i].cap);
        }
        flow += mf;
        for(int i = pre[t];~i;i = pre[edges[i^1].to]){
            edges[i].cap -= mf;
            edges[i^1].cap += mf;
            cost += mf * edges[i].cost;
        }
    }
    return cost;
}

int g[maxn][maxn];

int main()
{
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
    int s = 0,t = maxn - 1;
    tot = 0;
    memset(head,-1,sizeof(head));
    int n;
    cin>>n;
    for(int i = 1;i <= n;++i){
        addedges(s,i*2-1,1,0);
        addedges(i*2,t,1,0);
    }
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= n;++j){
            cin>>g[i][j];
            addedges(i*2-1,j*2,1,g[i][j]);
        }
    }
    int mi = mcmf(s,t);
//复原网络图
    tot = 0;
    memset(head,-1,sizeof(head));
    for(int i = 1;i <= n;++i){
        addedges(s,i*2-1,1,0);
        addedges(i*2,t,1,0);
    }
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= n;++j){
            addedges(i*2-1,j*2,1,g[i][j]);
        }
    }
    int mx = mxmf(s,t);
    printf("%d\n%d\n",mi,mx);
   return 0;
}