pigs.cpp

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include <assert.h>
#include <queue>
#include <vector>
#include <algorithm>
#include<math.h>
#include<iostream>
#define N (1005*2+2)
#define M (N*N+4*N)
#define Inf 0x3f3f3f3f
typedef long long LL;

using namespace std;

int pigs[N],pre[N];
struct edge {
  int v, cap, next;
};
edge e[M];

int head[N], level[N], cur[N];
int num_of_edges;

struct node{
	int x;
	int y;
	int maxx;
	int num;
}g[N];
/*
 * When there are multiple test sets, you need to re-initialize before each
 */
void dinic_init(void) {
  num_of_edges = 0;
  memset(head, -1, sizeof(head));
  return;
}

int add_edge(int u, int v, int c1, int c2) {
  int& i=num_of_edges;

  assert(c1>=0 && c2>=0 && c1+c2>=0); // check for possibility of overflow
  e[i].v = v;
  e[i].cap = c1;
  e[i].next = head[u];
  head[u] = i++;

  e[i].v = u;
  e[i].cap = c2;
  e[i].next = head[v];
  head[v] = i++;
  return i;
}

void print_graph(int n) {
  for (int u=0; u<n; u++) {
    printf("%d: ", u);
    for (int i=head[u]; i>=0; i=e[i].next) {
      printf("%d(%d)", e[i].v, e[i].cap);
    }
    printf("\n");
  }
  return;
}

/*
 * Find all augmentation paths in the current level graph
 * This is the recursive version
 */
int dfs(int u, int t, int bn) {
  if (u == t) return bn;
  int left = bn;
  for (int &i=cur[u]; i>=0; i=e[i].next) {
    int v = e[i].v;
    int c = e[i].cap;
    if (c > 0 && level[u]+1 == level[v]) {
      int flow = dfs(v, t, min(left, c));
      if (flow > 0) {
        e[i].cap -= flow;
        e[i^1].cap += flow;
        cur[u] = i;
        left -= flow;
        if (!left) break;
      }
    }
  }
  if (left > 0) level[u] = 0;
  return bn - left;
}

bool bfs(int s, int t) {
  memset(level, 0, sizeof(level));
  level[s] = 1;
  queue<int> q;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    if (u == t) return true;
    for (int i=head[u]; i>=0; i=e[i].next) {
      int v = e[i].v;
      if (!level[v] && e[i].cap > 0) {
        level[v] = level[u]+1;
        q.push(v);
      }
    }
  }
  return false;
}

LL dinic(int s, int t) {
  LL max_flow = 0;

  while (bfs(s, t)) {
    memcpy(cur, head, sizeof(head));
    max_flow += dfs(s, t, INT_MAX);
  }
  return max_flow;
}

int upstream(int s, int n) {
  int cnt = 0;
  vector<bool> visited(n);
  queue<int> q;
  visited[s] = true;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i=head[u]; i>=0; i=e[i].next) {
      int v = e[i].v;
      if (e[i].cap > 0 && !visited[v]) {
        visited[v] = true;
        q.push(v);
        cnt++;
      }
    }
  }
  return cnt; // excluding s
}
double calDis(int index1,int index2){
	return sqrt( pow(g[index1].x-g[index2].x,2) + pow(g[index1].y-g[index2].y,2) );
}
int main() {
   
   int m,n;
   while(cin>>m>>n){
   	memset(pre,0,sizeof(pre));
    memset(pigs,0,sizeof(pigs));
   	for(int i=1;i<=m;i++){
   		cin>>pigs[i];
	   }
	int s,e;
    s = 0;
    e = n+1;
    dinic_init();
   
   for(int i=1;i<=n;i++){
	   int k;
	   cin>>k;
	   int total = 0;
	   for(int j=0;j<k;j++){
	   	int tag;
	   	cin>>tag;
	   	if(pre[tag]==0){
	   		pre[tag] = i;
	   		total+=pigs[tag];
		   }else{
			  add_edge(pre[tag],i,Inf,0);
		   }
		
	   }
	   add_edge(s,i,total,0);
	   int need;
	   cin>>need;
	   add_edge(i,e,need,0);
     }
     int res = dinic(s,e);
     cout<<res<<endl;
  }
 
  return 0;
}