最小费用最大流。
建图方式如图所示
然后就是费用流的模板~~
把最小费用转化成最大费用，做法一样。< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+u7nT0NK71tbX9reoo6y+zcrHsNHL+dPQtcSx37XEt9HTw8ihuLqjrMi7uvPIpdfu0KG30dPDo6zIu7rzyKW4uiYjMjA1NDA7vs26w6Gjoa48L3A+CjxwPjxwcmUgY2xhc3M9"brush:java;">#include
#include
#include
#include
#include
using namespace std; #define INF 99999999 #define maxn 5050 #define LL long long struct list { int l; int r; int v; int f; int next; }node[1000001]; int num; int head[1000001]; int pre[maxn]; int n,k; int st,ed; LL ans; int ns; void add(int l,int r,int v,int f) { node[num].l=l; node[num].r=r; node[num].v=v; node[num].f=f; node[num].next=head[l]; head[l]=num++; node[num].l=r; node[num].r=l; node[num].v=-v; node[num].f=0; node[num].next=head[r]; head[r]=num++; } int bfs() { int visit[maxn]; int dist[maxn]; int i; for(i=0;i<=ns;i++)dist[i]=-1; memset(visit,0,sizeof(visit)); memset(pre,-1,sizeof(pre)); queue
q; q.push(0); dist[0]=0; visit[0]=1; while(!q.empty()) { int e=q.front(); q.pop(); visit[e]=0; for(i=head[e];i!=-1;i=node[i].next) { int r=node[i].r; if(dist[r]
0) { pre[r]=i; dist[r]=dist[e]+node[i].v; if(!visit[r]) { q.push(r); visit[r]=1; } } } } if(dist[ns]==-1)return 0; return 1; } void change() { int minx,i; minx=INF; for(i=pre[ns];node[i].l!=0;i=pre[node[i].l]) { minx=min(minx,node[i].f); } for(i=pre[ns];node[i].l!=0;i=pre[node[i].l]) { node[i].f-=minx; node[i^1].f+=minx; ans+=minx*node[i].v; } } int main() { int i,j; int ll,rr; while(~scanf("%d%d",&n,&k)) { memset(head,-1,sizeof(head)); num=0; int a; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%d",&a); ll=(i-1)*n+j; rr=ll+n*n; add(ll,rr,a,1); add(ll,rr,0,k-1); if(j