很诡异的是300WA但是100T掉了?
还是说这道题不能用纯费用流?
#include<bits/stdc++.h>
using namespace std;
#define maxx 2000001
#define S 1999999
#define T 2000000
#define opst 1000000
int fi[maxx],nx[maxx],to[maxx],val[maxx],co[maxx],pre[maxx],min_flow[maxx],in[maxx],dis[maxx],tot=1;
int min_cost,max_flow;
int L[1001][1001];
void link(int a,int b,int c,int d)
{
nx[++tot]=fi[a];
fi[a]=tot;
to[tot]=b;
val[tot]=c;
co[tot]=d;
nx[++tot]=fi[b];
fi[b]=tot;
to[tot]=a;
val[tot]=0;
co[tot]=-d;
}
bool spfa()
{
memset(dis,0x3f3f3f3f,sizeof(dis));
queue<int>que;
que.push(S);
min_flow[S]=0x7ffffff;
in[S]=1;
dis[S]=0;
while(!que.empty())
{
int x=que.front();
que.pop();
in[x]=0;
for(int i=fi[x];i;i=nx[i])
{
int v=to[i];
if(dis[x]+co[i]<dis[v]&&val[i])
{
dis[v]=dis[x]+co[i];
pre[v]=i;
min_flow[v]=min(min_flow[x],val[i]);
if(!in[v])
{
in[v]=1;
que.push(v);
}
}
}
}
return dis[T]<0x3f3f3f3f;
}
void ek()
{
while(spfa())
{
min_cost+=dis[T]*min_flow[T];
max_flow+=min_flow[T];
int x=T;
while(x!=S)
{
int i=pre[x];
val[i]-=min_flow[T];
val[i^1]+=min_flow[T];
x=to[i^1];
}
}
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>L[i][j];
link(S,i*1000+j,1,0);
link(i*1000+j+opst,T,1,0);
}
}
int k;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>k;
for(int s=L[i][j];s<=k;s++)
{
for(int r=0;r<m;r++)
{
link(i*1000+j,s*1000+r+opst,1,2*(abs(s-i))+min(abs(j-r),m-abs(j-r)));
}
}
}
}
ek();
if(max_flow!=n*m)
{
cout<<"no solution";
}
else
{
cout<<min_cost<<endl;
}
}