几乎是个板子，跟游戏几乎是重题。
将每行建点，每列建点，这样可以保证每行每列都只有一个。
格点拆掉，算个费用流就好了。
看代码：
#include<bits/stdc++.h> using namespace std; #define inf 1e9 const int maxn=100005; int beg[maxn],nex[maxn],to[maxn],w[maxn],f[maxn],e; inline void add(int x,int y,int z,int c){ nex[e]=beg[x];beg[x]=e; to[e]=y;f[e]=z;w[e]=c;e++; } int n,t,a[105][105]; inline int read(){ int x=0,f=1; char c=getchar(); while(c<'0'||c>'9'){ if(c=='-')f=-1; c=getchar(); } while(c>='0'&&c<='9'){ x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*f; } int dis[maxn],vis[maxn],flow[maxn],pre[maxn],las[maxn]; queue<int>q; inline int spfa(){ //puts("spfa"); memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); while(!q.empty())q.pop(); dis[0]=0; vis[0]=1; flow[0]=inf; pre[t]=-1; q.push(0); while(!q.empty()){ int x=q.front(); q.pop(); //printf("%d ",x); vis[x]=0; for(int i=beg[x];~i;i=nex[i]) if(f[i]&&dis[to[i]]>dis[x]+w[i]){ dis[to[i]]=dis[x]+w[i]; pre[to[i]]=x; las[to[i]]=i; flow[to[i]]=min(flow[x],f[i]); if(!vis[to[i]]){ vis[to[i]]=1; q.push(to[i]); } } } //printf("%d ",flow[t]); return pre[t]!=-1; } int main(){ memset(beg,-1,sizeof(beg)); n=read(); int x,cnt=0,pos; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ a[i][j]=read(),cnt++; add(cnt,cnt+n*n,1,a[i][j]); add(cnt+n*n,cnt,0,-a[i][j]); } cnt=2*n*n; t=++cnt; for(int i=1;i<=n;i++){ cnt++; add(0,cnt,1,0); add(cnt,0,0,0); for(int j=1;j<=n;j++){ pos=(i-1)*n+j; add(cnt,pos,inf,0); add(pos,cnt,0,0); } } for(int j=1;j<=n;j++){ cnt++; add(cnt,t,1,0); add(t,cnt,0,0); for(int i=1;i<=n;i++){ pos=(i-1)*n+j+n*n; add(pos,cnt,inf,0); add(cnt,pos,0,0); } } int maxflow=0; while(spfa()){ maxflow+=flow[t]*dis[t]; pos=t; while(pos!=0){ f[las[pos]]-=flow[t]; f[las[pos]^1]+=flow[t]; pos=pre[pos]; } } printf("%d ",maxflow); memset(beg,-1,sizeof(beg)); e=cnt=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ cnt++; add(cnt,cnt+n*n,1,-a[i][j]); add(cnt+n*n,cnt,0,a[i][j]); } cnt=2*n*n; t=++cnt; for(int i=1;i<=n;i++){ cnt++; add(0,cnt,1,0); add(cnt,0,0,0); for(int j=1;j<=n;j++){ pos=(i-1)*n+j; add(cnt,pos,inf,0); add(pos,cnt,0,0); } } for(int j=1;j<=n;j++){ cnt++; add(cnt,t,1,0); add(t,cnt,0,0); for(int i=1;i<=n;i++){ pos=(i-1)*n+j+n*n; add(pos,cnt,inf,0); add(cnt,pos,0,0); } } maxflow=0; while(spfa()){ maxflow-=flow[t]*dis[t]; pos=t; while(pos!=0){ f[las[pos]]-=flow[t]; f[las[pos]^1]+=flow[t]; pos=pre[pos]; } } printf("%d ",maxflow); return 0; }
深深地感到自己的弱小。