题解：
裸的最小、大费用最大流。
其实和最小费用最大流一样，只是推进去时费用取反，输出也取反。
代码：
#include<queue> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 105 #define ll long long const int inf = 0x3f3f3f3f; const ll Inf = 0x3f3f3f3f3f3f3f3fll; inline int rd() { int f=1,c=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch=getchar();} return f*c; } int n,S,T; struct Mcmf { int hed[2*N],cnt; Mcmf() { memset(hed,-1,sizeof(hed)); cnt=-1; } struct EG { int to,nxt; ll w,c; }e[N*N*2]; void ae(int f,int t,ll w,ll c) { e[++cnt].to = t; e[cnt].nxt = hed[f]; e[cnt].w = w; e[cnt].c = c; hed[f] = cnt; } ll fl[N],dis[N]; int fa[N],pre[N]; bool vis[N]; queue<int>q; bool spfa() { memset(dis,0x3f,sizeof(dis)); dis[S] = 0,fl[S] = Inf,vis[S] = 1; q.push(S); while(!q.empty()) { int u = q.front(); q.pop(); for(int j=hed[u];~j;j=e[j].nxt) { int to = e[j].to; if(e[j].w&&dis[to]>dis[u]+e[j].c) { dis[to] = dis[u]+e[j].c; fl[to] = min(fl[u],e[j].w); pre[to] = j,fa[to] = u; if(!vis[to]) { vis[to] = 1; q.push(to); } } } vis[u] = 0; } return dis[T]!=Inf; } ll mcmf() { ll ret = 0; while(spfa()) { ret+=fl[T]*dis[T]; int u = T; while(u!=S) { e[pre[u]].w-=fl[T]; e[pre[u]^1].w+=fl[T]; u = fa[u]; } } return ret; } }f1,f2; ll c[N][N]; int main() { n = rd(),S = 2*n+1,T = 2*n+2; for(int i=1;i<=n;i++) { f1.ae(S,i,1,0); f1.ae(i,S,0,0); f1.ae(i+n,T,1,0); f1.ae(T,i+n,0,0); f2.ae(S,i,1,0); f2.ae(i,S,0,0); f2.ae(i+n,T,1,0); f2.ae(T,i+n,0,0); } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { c[i][j] = rd(); f1.ae(i,j+n,1,c[i][j]); f1.ae(j+n,i,0,-c[i][j]); f2.ae(i,j+n,1,-c[i][j]); f2.ae(j+n,i,0,c[i][j]); } printf("%lld %lld ",f1.mcmf(),-f2.mcmf()); return 0; }