好題啊，才發(fā)現(xiàn)用網(wǎng)絡(luò)流也能解這么有實際意義的問題，說不定以后再工程中真的能遇到呢。
網(wǎng)絡(luò)上的方法是用KM,不過個人比較喜歡用最小費(fèi)用，就是跑得慢了點。
一點教訓(xùn)吧：這個題里面總點數(shù)應(yīng)該是2500+50+2
最小的邊數(shù)應(yīng)該是 (2500*50+50+2500)*2,剛開始沒有乘以2，結(jié)果猛RE.后來想到網(wǎng)絡(luò)流里是要建正反邊的，汗啊。
建圖的代碼如下：
int main()
{
int t ;
int i,j,k;
scanf("%d",&t);
while(t--)
{
len=0;
int tem;
scanf("%d%d",&m,&n);
for(i=0;i<n*m+m+2;i++)
adj[i]=NULL;
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
{
scanf("%d", &tem);
for (k = 0; k < m; k++)
insert(i,m+j*m+k,1,(k + 1) * tem);
}
int s=n*m+m;
int t=n*m+m+1;
for(i=0;i<m;i++)
insert(s,i,1,0);
for(i=m;i<n*m+m;i++)
insert(i,t,1,0);
printf("%.6lf\n",(double)mincostflow(t+1,s,t)/(double)m);
}
return 0;
}