//用N皇后改的，很勉强.
#include <iostream>
#include <string.h>
using namespace std;

const int  N=5;

int matrix[N][N]={1,  2,  3,  4,  5,
            2,  5, 4,  1,  4,
            6,  1,  4,  5,  0,
            10, 2,  1,  1,  3,
            5,  6,  9,  1,  1,
};

int max_sum;
int max_array[N];

bool is_right_pos(int * row_matrix,int row,int column)
{
    for(int k=0;k<row;k++)
        if(column==row_matrix[k])
            return false;
    return true;
}


void Trail(int i,int *b)
{
    static bool isfirst=true;
    if(i==N)
    {
        int sum=0;
        int k=0;
        for(;k<N;k++)
            sum+=matrix[k][b[k]];
        if(isfirst)
        {
            max_sum=sum;
            isfirst=false;
        }
        else
        {
            if(max_sum<sum)
            {
                max_sum=sum;
                memcpy(max_array,b,sizeof(int)*N);
            }
        }
    }
    else
    {
        for(int j=0;j<N;j++)
            if(is_right_pos(b,i,j))
            {
                b[i]=j;
                Trail(i+1,b);
            }
    }
}

void main()
{
    int row_matrix[N];

    Trail(0,row_matrix);

    cout<<"the max sum array is:";

    for(int i=0;i<N;i++)
        cout<<matrix[i][max_array[i]]<<" ";

    cout<<"the max sum is:"<<max_sum<<endl;
}
    

#include <stdio.h>
#include <stdlib.h>
#define M 100
#define N 100
int main(){
    int a[N][M],i,j,n,m;
    int sum=0,max;
    printf("input n and m:");
    scanf("%d",&n);
    scanf("%d",&m);
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
            scanf("%d",&a[i][j]);
    j=0;
    for(i=0;i<n;i++)
    {
         max=a[i][j];
        for(j=0;j<m;j++)
        {
            if(a[i][j]>max)
                max=a[i][j];
        }
        sum+=max;
    }
    sum=sum/m;
    printf("%d",sum);
    return 0;
}

#include   <iostream>   
#include   <iomanip>   
#include   <fstream>   
#include   <cstdio>
#include   <memory>   
using namespace std;

const   int   Max=50;   
bool   T[Max],R[Max],visited[Max];   
int   U[Max],V[Max],gt[Max][Max],x[Max],y[Max];   
int   N;   

int   path(int   u)   
{   
    int   v;   
    for(v=0;v<N;v++)   
    {   
        if(U[u]+V[v]-gt[u][v]==0   &&   !visited[v])   
        {   
            visited[v]=1;   
            if(y[v]<0   ||   path(y[v]))   
            {   
                x[u]=v;y[v]=u;   
                R[u]=1;T[v]=0;   
                return   1;   
            }else{   
                T[v]=1;   
                R[y[v]]=0;   
            }   
        }   
    }   
    return   0;   
}   

int   main()   
{   
//    freopen("1.in","r",stdin);
    int   i,j,ans,sigma,step=0;   
    while(scanf("%d", &N) != EOF){   
        for(i=0;i<N;i++)   
        {   
            U[i]=V[i]=0;   
            for(j=0;j<N;j++)   
            {   
                scanf("%d", &gt[i][j]);
                if(U[i]<gt[i][j])U[i]=gt[i][j];   
            }   
        }   
        //////////////////////////////////////////////////////////   
        for(;;)   
        {   
            ans=0;   
            sigma=0;   
            memset(x,-1,sizeof(x));   
            memset(y,-1,sizeof(y));   
            memset(R,0,sizeof(R));   
            memset(T,0,sizeof(T));   
            for(i=0;i<N;i++)   
            {   
                if(x[i]<0)   
                {   
                    memset(visited,0,sizeof(visited));   
                    ans+=path(i);   
                }   
            }   
            for(i=0;i<N;i++)   
            {   
                if(!R[i])   
                    for(j=0;j<N;j++)   
                    {   
                        if(!T[j]   &&   (sigma<1   ||   sigma>U[i]+V[j]-gt[i][j]   &&   U[i]+V[j]-gt[i][j]>0))   
                            sigma=U[i]+V[j]-gt[i][j];     
                    }   
            }   

            if(ans>=N)   
                break;   

            for(i=0;i<N;i++)   
            {   
                if(!R[i])   
                    U[i]-=sigma;   
                if(T[i])   
                    V[i]+=sigma;   
            }   
        }   
        /////////////////////////////////////////////////////////   
        ans=0;   
        for(i=0;i<N;i++)   
        {   
            ans+=U[i]+V[x[i]];    
        }   
        printf("%d\n", ans);
    }   
    return   0;   
}