大意:

有M个猪圈，每个猪圈里初始时有若干头猪。一开始所有猪圈都是关闭的。依次来了N个顾客，每个顾客分别会打开指定的几个猪圈，从中买若干头猪。每个顾客分别都有他能够买的数量的上限。每个顾客走后，他打开的那些猪圈中的猪，都可以被任意地调换到其它开着的猪圈里，然后所有猪圈重新关上。问总共最多能卖出多少头猪。（1 <= N <= 100, 1 <= M <= 1000）

构造这个网络模型的规则：

? 每个顾客分别用一个结点来表示。

? 对于每个猪圈的第一个顾客，从源点向他连一条边，容量就是该猪圈里的猪的初始数量。如果从源点到一名顾客有多条边，则可以把它们合并成一条，容量相加。
? 对于每个猪圈，假设有n个顾客打开过它，则对所有整数i∈[1, n)，从该猪圈的第i个顾客向第i + 1个顾客连一条边，容量为∞。
? 从各个顾客到汇点各有一条边，容量是各个顾客能买的数量上限。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; const int maxn = 1000 + 50; const int INF = 1e9; int n, m; struct Edge{ int from, to, cap, flow; }; struct Dinic{ int n, m, s, t; vector
        
          edges; vector
         
           G[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; void init(int n) { this->n = n; for(int i=0; i<=n; ++i) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int cap) { edges.push_back((Edge){ from, to, cap, 0 }); edges.push_back((Edge){ to, from, 0, 0 }); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS(){ memset(vis, 0, sizeof vis ); queue
          
            Q; Q.push(s); vis[s] = 1; d[s] = 0; while(!Q.empty()){ int x = Q.front(); Q.pop(); for(int i=0; i
           
             e.flow){ vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a){ if(x==t || a==0) return a; int flow = 0, f; for(int& i=cur[x]; i
            
             0){ e.flow += f; edges[G[x][i]^1].flow -= f; flow += f; a -= f; if(a==0) break; } } return flow; } int MaxFlow(int s, int t){ this->s = s; this->t = t; int flow = 0; while(BFS()){ memset(cur, 0, sizeof cur ); flow += DFS(s, INF); } return flow; } }; Dinic gao; int pig[maxn], pre[maxn]; void fk() { int A, B, K; int s = 0, t = n + 1; gao.init(t+2); memset(pre, 0, sizeof pre ); for(int i=1; i<=m; ++i){ scanf("%d", &pig[i]); } for(int i=1; i<=n; ++i){ scanf("%d", &A); for(int j=1; j<=A; ++j){ scanf("%d", &K); if(!pre[K]){ gao.AddEdge(s, i, pig[K]); }else { gao.AddEdge(pre[K], i, INF); } pre[K] = i; } scanf("%d", &B); gao.AddEdge(i, t, B); } int ans = gao.MaxFlow(s, t); printf("%d\n", ans); } int main() { // freopen("in.txt", "r",stdin); while(~scanf("%d%d", &m, &n)){ fk(); } return 0; }