In a weird high school, there are $$$n$$$ students, and the school principal Mr. X wants to make students happy so he decides to throw a couples' party.
In this high school, between every 2 person, there can be 4 types of relationships:
1: they love each other
2: The first loves the second but the second doesn't
3: The second loves the first but the first doesn't
4: they don't like each other
At this party, people will be grouped into Pairs of couples.
The relationship between them determines the happiness of a pair:
type 1: happiness 2, type 2,3: happiness 1, type 4: happiness -1
if a person gets left out(I.E n is odd) there will be a -2 happiness for him
Since Mr. X is a happy person he wants to maximize the sum happiness of the party. Since he is a busy person He asks you to do that
Input Format
In The First Line, there will be one integer $$$n$$$: $$$n$$$, ($$$1 \leq n \leq 10^5$$$) the number of people at the party. In the Second line will be $$$m$$$, the number of people who love a person ($$$1 \leq r \leq 10^5$$$)
In the following $$$m$$$ lines there will be a format: two indexes $$$i$$$, $$$j$$$ meaning the person $$$i$$$ loves the person $$$j$$$. (Two-sided love will be given in 2 separate lines, if there isn't a directed edge between 2 people their relationship is type 4)
Output Format In the only line of the output, print the maximum happiness of the party
So today I came up with this problem and actually got stuck in solving it. Appreciate any helps
Naturally, you always want to pair as many people as possible since the happiness of any couple ($$$2$$$, $$$1$$$ or $$$-1$$$) is larger than the happiness of two single people ($$$-4$$$).
This means that we will have $$$\left\lfloor n/2\right\rfloor$$$ couples. Let's add $$$-\left\lfloor n/2\right\rfloor$$$ to the answer (and an extra $$$-2$$$ if $$$n$$$ is odd), and let's increase the happiness of every couple by $$$1$$$, making the happines of type 1 couples $$$3$$$, happiness of type 2 and 3 couples $$$2$$$ and happiness of type 4 couples $$$0$$$.
Let's create a new graph containing all people as nodes. For any two people who would form a type 1 couple , add an edge of weight $$$3$$$ between them. For any two people who would form a type 2 or 3 couple, add an edge of weight $$$2$$$ between them. Now, the maximum total happiness is equal to the maximum weight matching of this graph (plus whatever we already added to the answer).
As there are no constraints on how people can love each other, your problem is equivalent to maximum weight matching on a general graph with all edge weights being $$$2$$$ or $$$3$$$. I don't really know anything about solving maximum weight matchings on general graphs with limited edge weights, so I don't know how efficiently this can be solved.
P.S. I don't think this is a 1700 problem :D
Nicee, the idea to assign a value to every kind of relationship and subtracting the additional value was really nice
Thanks for the explanation
And the graph is simple and may be cyclic
Nice! What do you think the rating would be for the problem?
2000+
Can you give me the problem link..
read the last line of the blog