#include<bits/stdc++.h>
using namespace std;
const int inf=1061109567;
const int M=105;
bool sx[M],sy[M];
int match[M],w[M][M],n,m,d,lx[M],ly[M],a[M],cnt;
void init()
{
memset(w,0,sizeof(w));
}
bool dfs(int u)
{
int v;
sx[u]=true;
for(v=0;v<m;v++)
{
if(!sy[v]&&lx[u]+ly[v]==w[u][v])
{
sy[v]=true;
if(match[v]==-1||dfs(match[v]))
{
match[v]=u;
return true;
}
}
}
return false;
}
int KM()
{
int i,j,k,sum=0;
memset(ly,0,sizeof(ly));
for(int i=0;i<n;i++)
{
lx[i]=-inf;
for(int j=0;j<m;j++)
if(lx[i]<w[i][j])
lx[i]=w[i][j];
}
memset(match,-1,sizeof(match));
for(int i=0;i<n;i++)
while(1)
{
memset(sx,false,sizeof(sx));
memset(sy,false,sizeof(sy));
if (dfs(i))
break;
d=inf;
for(int j=0;j<n;j++)
if(sx[j])
for(int k=0;k<m;k++)
if(!sy[k])
d=min(d,lx[j]+ly[k]-w[j][k]);
if(d==inf)
return 01;
for(int j=0;j<n;j++)
if(sx[j])
lx[j]-=d;
for(int j=0;j<m;j++)
if(sy[j])
ly[j]+=d;
}
for(int i=0;i<m;i++)
if(match[i]>-1)
{
sum+=w[match[i]][i];
a[++cnt]=i+1;
}
return sum;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&w[i][j]);
int ans=KM();
cout<<ans<<endl;
for(int i=1;i<=cnt;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
求dalao查错,感谢