Ryan_<

T1 hero

n轮游戏，每轮m个数中选择两个不同位置的数，第i轮选择第j个数花费的代价为/(w[i][j]/)，从上一轮的a位置切换到当前轮的b位置的额外代价为/(K*|a-b|/)。求最小花费。

0%普及组dp O(N^5)

i-1==>i，显然可以优化空间。

30%最小费用最大流 N<=50,O(N^4)

思路源于今天做的SDOI2016 数字配对。

建图很简单，想的时间有点长，建两个原点控制一下流的次数2.

网络流细节总出错啊：

数组不要以为开到10^6就足够了！点数和边数计算不能着急！

点数=2*m*n+3 O(n^2)

边数=2*m+m*n+m*m*(n-1) 至少O(n^3)

满足“除了原点和汇点外，每个点要么只有一条入弧，容量为1，要么只有一条出弧，容量为1”，

单位网络的网络流复杂度O(√n*m)

这样就是O(n^4)

边一定要开大！自己算算50^2,50^4就多少了！但这只是下界啊！！常数级别的缩小也会导致RE、TLE、WA到很惨！

以后一定要写数据生成器，像这么丝帛的错误拍一下就看出来了啊！！

const int N=200005,M=3000005;
int n,m,K;int w[305][305];
int S,SS,T,num;int ans;
int head[N],from[M<<1],tot=1;
struct edge{int fro,go,nxt;int v,c;}e[M<<1];
void addedge(int x,int y,int z1,int z2)
{
	e[++tot]=(edge){x,y,head[x],z1,z2};head[x]=tot;
	e[++tot]=(edge){y,x,head[y],0,-z2};head[y]=tot;
}
bool inq[N];int d[N];
bool spfa()
{
	queue<int> q;
	mec(inq,0);
	F(i,1,T) d[i]=inf;
	q.push(SS);d[SS]=0;inq[SS]=1;
	while(!q.empty()){
		int x=q.front();q.pop();inq[x]=0;
		R(i,x){
			int y=e[i].go;
			if(e[i].v&&d[y]>d[x]+e[i].c){
				d[y]=d[x]+e[i].c;
				from[y]=i;
				if(!inq[y]){
					inq[y]=1;
					q.push(y);
				}
			}
		}
	}
	return d[T]!=inf;
}
void mcf()
{
  while(spfa()){
		int tmp=inf;
		for(int i=from[T];i;i=from[e[i].fro]) tmp=min(tmp,e[i].v);
		ans+=d[T]*tmp;
		for(int i=from[T];i;i=from[e[i].fro]){e[i].v-=tmp;e[i^1].v+=tmp;}	
	}
}
void readit()
{
	n=read();m=read();K=read();
	F(i,1,n) F(j,1,m) w[i][j]=read();
}
//#define p(x,y) (((x)-1)*m+(y));
int p(int x,int y){return (x-1)*m+y;}
void debug()
{
	for(int i=2;i<=tot;i+=2){
		cout<<e[i].fro<<' '<<e[i].go<<' '<<e[i].v<<' '<<e[i].c<<endl;
		cout<<e[i^1].fro<<' '<<e[i^1].go<<' '<<e[i^1].v<<' '<<e[i^1].c<<endl;
		cout<<endl;
	}
}
void init()
{
	num=n*m;SS=num*2+1;
	S=num*2+2,T=num*2+3;
	F(i,1,m) addedge(S,p(1,i),1,0);
	F(i,1,n) F(j,1,m) addedge(p(i,j),p(i,j)+num,1,w[i][j]);
	F(i,1,n-1) F(j,1,m) F(k,1,m) addedge(p(i,j)+num,p(i+1,k),1,K*abs(k-j));
	F(i,1,m) addedge(p(n,i)+num,T,1,0);
	addedge(SS,S,2,0);
}
void solve()
{
	ans=0;
	mcf();
	printf("%d\n",ans);
}
int main()
{
	freopen("hero.in","r",stdin);
	freopen("hero.out","w",stdout);
	readit();
	init();
	solve();
	return 0;
}

100%  N<=300,O(N^3)

思路一：

网络流复杂度不太靠谱，我就敲了个暴力还悻悻地觉得可能是正解真是太naive。

但是大多数边都容量都是1，一定能找到更优的建图方案。

考虑分层图。

思路二：

从dp优化方向来考虑。