比较简单,如果直观的建图的话,记录一下费用流模板
#include<bits/stdc++.h> using namespace std; const int N=3e5+10; const int inf=0x3f3f3f3f; int h[N],ne[N],e[N],idx,w[N],f[N]; int d[N],pre[N],incf[N],S,T; int st[N]; void add(int a,int b,int c,int d){ e[idx]=b,ne[idx]=h[a],f[idx]=c,w[idx]=d,h[a]=idx++; e[idx]=a,ne[idx]=h[b],f[idx]=0,w[idx]=-d,h[b]=idx++; } bool spfa(){ memset(d,0x3f,sizeof d); memset(incf,0,sizeof incf); incf[S]=inf; queue<int> q; q.push(S); d[S]=0; while(q.size()){ auto t=q.front(); q.pop(); st[t]=0; for(int i=h[t];i!=-1;i=ne[i]){ int j=e[i]; if(f[i]&&d[j]>d[t]+w[i]){ d[j]=d[t]+w[i]; pre[j]=i; incf[j]=min(f[i],incf[t]); if(!st[j]){ q.push(j); st[j]=1; } } } } if(incf[T]>0) return true; else return false; } int EK(){ int cost=0; while(spfa()){ int t=incf[T]; cost+=t*d[T]; for (int i=T;i!=S;i=e[pre[i]^1]){ f[pre[i]] -= t; f[pre[i]^1] += t; } } return cost; } int main(){ memset(h,-1,sizeof h); int n; cin>>n; S=0,T=2*n+1; int i,j; for(i=1;i<=n;i++){ add(S,i,1,0); add(i+n,T,1,0); for(j=1;j<=n;j++){ int x; cin>>x; add(i,j+n,1,x); } } cout<<EK()<<endl; for(i=0;i<idx;i+=2){ f[i]+=f[i^1],f[i^1]=0; w[i]=-w[i],w[i^1]=-w[i^1]; } cout<<-EK()<<endl; }