I've been looking trough the previous discussions on this problem.
Could anyone explain me why where they talking about a biparty graph?
Maybe I don't know the meaning of 'biparty', but I thought it's a
graph with vertexes divided into 2 groups, and any 2 vertexes from
one group are not adjacent.

Please give me some hints or explain me the problem.
As far as I understood, I have to find a transveral with maximum
sum,and output the sum all elements of the matrix minus the sum of
elements of transversal with maximum sum.

This problem usually have such description:
There are N wokers and N jobs.
For each pair of woker_i & job_j we know A[i,j].
A[i,j] - amount of money, that must be paid to the worker i, if he
done job j.
Necessary find assigment with such requipments:
  1)One worker can done, only one job.
  2)Each job must be done.
  3)Sum of money that paid is minimum.

It classical name "Assigment problem".

We can construct such biparty graph.
First party - N nodes (workers)
Second party - N nodes (jobs)
The edge between i & j has weight A[i,j].

Than we must find perfect matching on this graph such, that total sum
weight of the edges that belongs to this matching be as minimum as
possible.

We can use Hungarian(Kuhn-Munkers) algorithm or Bradford method to
solve this problem. (Second is slowler, but simpler).

But, in this problem, finding transversal with minimum sum is the
same.

P.S. I am interesting, how you find transversal with minimum/maximum
sum?

Andrey Popyk.
E-Mail: popyk@ief.km.ua
ICQ# 88914410

About transversal - if workers have to do jobs (a1,a2,...,an),
then the transversal (1,a1),(2,a2), ... , (n,an) is the one with
minimal sum.