Back in the euphoric early days of the Web, people liked to claim that much of the enormous potential in a company like Yahoo!

Back in the euphoric early days of the Web, people liked to claim that much of the enormous potential in a company like Yahoo! was in the "eyeballs"—the simple fact that millions of people look at its pages every day. Further, by convincing people to register personal data with the site, a site like Yahoo! can show each user an extremely targeted advertisement whenever he or she visits the site, in a way that TV networks or magazines couldn't hope to match. So if a user has told Yahoo! that he or she is a 20-year-old computer science major from Cornell University, the site can present a banner ad for apartments in Ithaca, New York; on the other hand, if he or she is a 50-year-old investment banker from Greenwich, Connecticut, the site can display a banner ad pitching Lincoln Town Cars instead.

But deciding on which ads to show to which people involves some serious computation behind the scenes. Suppose that the managers of a popular Web site have identified k distinct demographic groups G1, G2, . . . , Gk. (These groups can overlap; for example, G1 can be equal to all residents of New York State, and G2 can be equal to all people with a degree in computer science.) The site has contracts with m different advertisers, to show a certain number of copies of their ads to users of the site. Here's what the contract with the ith advertiser looks like. 

• . For a subset Xi ⊆ {G1, . . . , Gk} of the demographic groups, advertiser i wants its ads shown only to users who belong to at least one of the demographic groups in the set Xi.
• . For a number ri, advertiser i wants its ads shown to at least ri users each minute. 

Now consider the problem of designing a good advertising policy— a way to show a single ad to each user of the site. Suppose at a given minute, there are n users visiting the site. Because we have registration information on each of these users, we know that user j (for j = 1, 2, . . . , n) belongs to a subset Uj ⊆ {G1, . . . , Gk} of the demographic groups. The problem is: Is there a way to show a single ad to each user so that the site's contracts with each of the m advertisers is satisfied for this minute? (That is, for each i=1,2,...,m, can at least ri of the n users, each belonging to at least one demographic group in Xi, be shown an ad provided by advertiser i ?)

Give an efficient algorithm under the context of flow network to decide if this is possible, and if so, to actually choose an ad to show each user.