洛谷p4014
#include<bits/stdc++.h>
using namespace std;
const int N=120;
const int M=N*N+(N<<1);
struct edge{int v,c,w,ne;}e[M];
int h[N],id=1;
int n,s,t;
int p[N][N],pre[N],mf[N],d[N];
bool vis[N];
void add(int u,int v,int c,int w){e[++id]={v,c,w,h[u]};h[u]=id;
}bool spfa(){memset(d,0x3f,sizeof(d));memset(mf,0,sizeof(mf));queue<int> q;q.push(s);d[s]=0;mf[s]=1e9;vis[s]=true;while(q.size()){int u=q.front();q.pop();vis[u]=false;for(int i=h[u];i;i=e[i].ne){int v=e[i].v;int w=e[i].w;if(d[v]>d[u]+w&&e[i].c){d[v]=d[u]+w;pre[v]=i;mf[v]=min(mf[u],e[i].c);if(!vis[v]){q.push(v);vis[v]=true;}}}}return mf[t]>0;
}int EK(){int flow=0,cost=0;while(spfa()){int v=t;while(v^s){int i=pre[v];e[i].c-=mf[t];e[i^1].c+=mf[t];v=e[i^1].v;}flow+=mf[t];cost+=mf[t]*d[t];}return cost;
}int main(){cin.tie(nullptr)->sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>p[i][j];}}//权值为费用for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int x=p[i][j];add(i,j+n,1,x);add(j+n,i,0,-x);}}s=0;t=n+n+1;for(int i=1;i<=n;i++){add(s,i,1,0);add(i,s,0,0);}for(int i=1;i<=n;i++){add(i+n,t,1,0);add(t,i+n,0,0);}//求最小权值和，跑最小费cout<<EK()<<endl;//清空原图memset(h,0,sizeof(h));id=1;//用权值取反建边for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int x=p[i][j];add(i,j+n,1,-x);add(j+n,i,0,x);}}for(int i=1;i<=n;i++){add(s,i,1,0);add(i,s,0,0);}for(int i=1;i<=n;i++){add(i+n,t,1,0);add(t,i+n,0,0);}//最小费的负数就是最大权值和cout<<-EK()<<endl;return 0;
}