最小費用最大流。
建圖方式如圖所示
然後就是費用流的模板~~
把最小費用轉化成最大費用，做法一樣。<喎?http://www.Bkjia.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));
queueq;
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
