Need help in an 1700ish graph problem

Revision en2, by bgopc, 2024-02-20 19:58:39

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

Tags graphs, dp on graphs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English bgopc 2024-02-20 19:58:39 80
en1 English bgopc 2024-02-20 19:54:40 1461 Initial revision (published)