TradingCards

You’ve decided to get rid of your Trading Card Game (TCG) collection. The possible financial activities are as follows:
- You can sell individual cards to Bearimy’s Card Emporium.
- You can buy individual cards from Bearimy’s Card Emporium.
- Card price is the same regardless of the transaction (buy or sell) with the Emporium.
- You can sell a set of cards (called a collection) to your friend Jeremy. Jeremy enjoys showing off different collection sets, so Jeremy will buy multiple sets but only one of each set. You have to, of course, have the cards in a set to be able to sell such set to Jeremy.
- If a card is needed in different collection sets, you only need one copy of that card (and not multiple copies of that card) to form all those sets to sell to Jeremy; you need the other cards in the sets as well. For example, if cards {1,2} is a set, cards {2,3} is a set, and cards {1,3,4} is a set, to sell these three sets to Jeremy, you only need one of each card 1, 2, 3, and 4.
- Jeremy only buys collection sets and not individual cards.

- A collection set is not necessarily more/less expensive than the sum of its component cards.

Given a list of cards, including their card shop cost and whether you own them, and a list of collection sets and the value Jeremy will pay for those sets, determine the maximum amount of money you can earn. This is done by buying from (and/or selling to) the card shop and selling the sets to Jeremy. Note that you choose what to buy from (and/or sell to) the card shop and what to sell to Jeremy. Your earning will be:

(cards sold to the shop) + (sets sold to Jeremy) – (cards bought from the shop)

The first input line contains an integer, n (1 ≤ n ≤ 50), representing the number of cards. Each of the next n input lines contains two integers: v_i (1 ≤ v_i ≤ 10000), representing the Bearimy card value, and h_i (0 ≤ h_i ≤ 1), representing whether you currently own the card (h_i= 1) or not (h_i = 0).

The cards are provided in the order of indices (1-indexed).

Following the individual card specification will be the description for the collection sets. The first input line in this section contains an integer, m (1 ≤ m ≤ 50), representing the number of sets. The set descriptions follow, each set consisting of two consecutive input lines. The first line of each set description contains two integers: c_j (1 ≤ c_j ≤ n), representing the number of cards in the set, and w_j (1 ≤ w_j ≤ 10000), representing the value of the set. The second input line of each set description contains cj distinct positive integers between 1 and n; these values represent the indices (1-indexed) of the cards that belong to the set.

#include<iostream> #include<cstring> using namespace std; const int N = 110,M = 6010,INF = 1e9; int h[N],ne[M],e[M],f[M],idx,n,m,S,T; int q[N],dep[N]; void add(int x,int y,int v){ ne[idx]=h[x],e[idx]=y,f[idx]=v,h[x]=idx++; } bool bfs(){ int hh=0,tt=-1; memset(dep,0,sizeof dep); dep[S] = 1,q[++tt] = S; while(hh<=tt){ int t = q[hh++]; for(int i=h[t];~i;i=ne[i]){ int j=e[i]; if(f[i]&&!dep[j]){ dep[j] = dep[t]+1;q[++tt] = j; } } } return dep[T]; } int dfs(int u,int in){ if(u==T) return in; int out = 0; for(int i=h[u];~i;i=ne[i]){ int j=e[i]; if(dep[j]==dep[u]+1&&f[i]){ int temp = dfs(j,min(in,f[i])); f[i]-=temp,f[i^1]+=temp; in-=temp,out+=temp; } } if(out==0) dep[u]=0; return out; } int dinic(){ int ans = 0; while(bfs()) ans+=dfs(S,INF); return ans; } int main() { memset(h,-1,sizeof h); S = 101,T = 102; cin>>n;int ans=0; for(int i=1;i<=n;i++){ int w,vis;scanf("%d%d",&w,&vis); add(i,T,w),add(T,i,0); if(vis) ans+=w; } cin>>m; for(int i=n+1;i<=n+m;i++){ int cnt,w;scanf("%d%d",&cnt,&w); ans+=w; add(S,i,w),add(i,S,0); for(int j=1,x;j<=cnt;j++){ scanf("%d",&x);add(i,x,INF),add(x,i,0); } } cout<<ans-dinic()<<endl; return 0; }

详情