POJ 1149 PIGS ，最大流

POJ 1149 PIGS ，最大流

大意:

有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]; i0){
				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;
}