Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
DJ and Mark are very lazy guys. These are not the guys from some game, these are the ones playing games all the time. Recently, they bought a new game named "Graph Vertices chooser". The rules of this game are pretty simple. It's a two-player game with each player taking alternating turns starting with DJ. You are given a weighed graph. All the vertices are initially unmarked. In each turn, a player chooses an unmarked vertex and mark it to red or black colour (DJ marks red whereas Mark marks black). The game ends when there is no any unmarked vertex left. After the end of the game, DJ's score will be weight of all the edges in graph such that both the end points of the edge are coloured red. Similarly, score of Mark is sum of weight of edges with both end points being black. DJ would like to maximize difference between his and Mark points, while Mark would like to minimize the difference between DJ's and his score. Both players optimally. Now, you are the one who decided to be the coach of both the players. You want to create many graphs for DJ and Mark to train. For that, you decided to take a graph H of N vertices. Initially, there is no edge in graph H. One by one, you will add an edge in the graph H and ask the both the players to play on the newly created graph. You will add M such edges. For each of the M graphs, you have to tell the difference between points of DJ and Mark at the end of the game, when they play the game on that graph. Note that self-loops and multi-edges are allowed to exist. Develop C++ develop code for the problem. Input: 1 54 121 131 141 151 Output: 1 1

DJ and Mark are very lazy guys. These are not the guys from some game, these are the ones playing games all the time. Recently, they bought a new game named "Graph Vertices chooser". The rules of this game are pretty simple. It's a two-player game with each player taking alternating turns starting with DJ. You are given a weighed graph. All the vertices are initially unmarked. In each turn, a player chooses an unmarked vertex and mark it to red or black colour (DJ marks red whereas Mark marks black). The game ends when there is no any unmarked vertex left. After the end of the game, DJ's score will be weight of all the edges in graph such that both the end points of the edge are coloured red. Similarly, score of Mark is sum of weight of edges with both end points being black. DJ would like to maximize difference between his and Mark points, while Mark would like to minimize the difference between DJ's and his score. Both players optimally. Now, you are the one who decided to be the coach of both the players. You want to create many graphs for DJ and Mark to train. For that, you decided to take a graph H of N vertices. Initially, there is no edge in graph H. One by one, you will add an edge in the graph H and ask the both the players to play on the newly created graph. You will add M such edges. For each of the M graphs, you have to tell the difference between points of DJ and Mark at the end of the game, when they play the game on that graph. Note that self-loops and multi-edges are allowed to exist. Develop C++ develop code for the problem. Input: 1 54 121 131 141 151 Output: 1 1

Database System Concepts
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
See similar textbooks
icon
Related questions
Question

Please help me in computer engineering question

DJ and Mark are very lazy guys. These are not the guys from some game, these are the ones playing games all the time. Recently, they bought a new game named "Graph Vertices chooser". The rules of this game are pretty simple. It's a two-player game with each player taking alternating turns starting with DJ. You are given a weighed graph. All the vertices are initially unmarked. In each turn, a player chooses an unmarked vertex and mark it to red or black colour (DJ marks red whereas Mark marks black). The game ends when there is no any unmarked vertex left. After the end of the game, DJ's score will be weight of all the edges in graph such that both the end points of the edge are coloured red. Similarly, score of Mark is sum of weight of edges with both end points being black. DJ would like to maximize difference between his and Mark points, while Mark would like to minimize the difference between DJ's and his score. Both players optimally. Now, you are the one who decided to be the coach of both the players. You want to create many graphs for DJ and Mark to train. For that, you decided to take a graph H of N vertices. Initially, there is no edge in graph H. One by one, you will add an edge in the graph H and ask the both the players to play on the newly created graph. You will add M such edges. For each of the M graphs, you have to tell the difference between points of DJ and Mark at the end of the game, when they play the game on that graph. Note that self-loops and multi-edges are allowed to exist. Develop C++ develop code for the problem. Input: 1 54 121 131 141 151 Output: 1
Transcribed Image Text:DJ and Mark are very lazy guys. These are not the guys from some game, these are the ones playing games all the time. Recently, they bought a new game named "Graph Vertices chooser". The rules of this game are pretty simple. It's a two-player game with each player taking alternating turns starting with DJ. You are given a weighed graph. All the vertices are initially unmarked. In each turn, a player chooses an unmarked vertex and mark it to red or black colour (DJ marks red whereas Mark marks black). The game ends when there is no any unmarked vertex left. After the end of the game, DJ's score will be weight of all the edges in graph such that both the end points of the edge are coloured red. Similarly, score of Mark is sum of weight of edges with both end points being black. DJ would like to maximize difference between his and Mark points, while Mark would like to minimize the difference between DJ's and his score. Both players optimally. Now, you are the one who decided to be the coach of both the players. You want to create many graphs for DJ and Mark to train. For that, you decided to take a graph H of N vertices. Initially, there is no edge in graph H. One by one, you will add an edge in the graph H and ask the both the players to play on the newly created graph. You will add M such edges. For each of the M graphs, you have to tell the difference between points of DJ and Mark at the end of the game, when they play the game on that graph. Note that self-loops and multi-edges are allowed to exist. Develop C++ develop code for the problem. Input: 1 54 121 131 141 151 Output: 1
Expert Solution
steps

Step by step

Solved in 2 steps with 1 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Knowledge Booster
Hyperlinks
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education
SEE MORE TEXTBOOKS