luogu1231 教辅的组成

注意把书拆成两份
#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

using namespace std;

int nb, nc, na, hea[40005], cnt, cur[40005], ss, tt, uu, vv, ww, maxFlow;

int lev[40005];

const int oo=0x3f3f3f3f;

queue<int> d;

struct Edge{

	int too, nxt, val;

}edge[150005];

void add_edge(int fro, int too, int val){

	edge[cnt].nxt = hea[fro];

	edge[cnt].too = too;

	edge[cnt].val = val;

	hea[fro] = cnt++;

}

void addEdge(int fro, int too, int val){

	add_edge(fro, too, val);

	add_edge(too, fro, 0);

}

bool bfs(){

	memset(lev, 0, sizeof(lev));

	lev[ss] = 1;

	d.push(ss);

	while(!d.empty()){

		int x=d.front();

		d.pop();

		for(int i=hea[x]; i!=-1; i=edge[i].nxt){

			int t=edge[i].too;

			if(!lev[t] && edge[i].val>0){

				lev[t] = lev[x] + 1;

				d.push(t);

			}

		}

	}

	return lev[tt]!=0;

}

int dfs(int x, int lim){

	if(x==tt)	return lim;

	int addFlow=0;

	for(int &i=cur[x]; i!=-1 && addFlow<lim; i=edge[i].nxt){

		int t=edge[i].too;

		if(lev[t]==lev[x]+1 && edge[i].val>0){

			int tmp=dfs(t, min(lim-addFlow, edge[i].val));

			edge[i].val -= tmp;

			edge[i^1].val += tmp;

			addFlow += tmp;

		}

	}

	return addFlow;

}

void dinic(){

	while(bfs()){

		for(int i=0; i<=tt; i++)	cur[i] = hea[i];

		maxFlow += dfs(ss, oo);

	}

}

int main(){

	memset(hea, -1, sizeof(hea));

	cin>>nb>>nc>>na;

	ss = 0; tt = nb + nb + nc + na + 1;

	cin>>ww;

	while(ww--){

		scanf("%d %d", &uu, &vv);

		addEdge(vv, uu+nc, 1);

	}

	cin>>ww;

	while(ww--){

		scanf("%d %d", &uu, &vv);

		addEdge(uu+nc+nb, vv+nb+nc+nb, 1);

	}

	for(int i=1; i<=nc; i++)

		addEdge(ss, i, 1);

	for(int i=nc+1; i<=nc+nb; i++)

		addEdge(i, i+nb, 1);

	for(int i=nb+nc+nb+1; i<=nb+nc+na+nb; i++)

		addEdge(i, tt, 1);

	dinic();

	cout<<maxFlow<<endl;

	return 0;

}
巴特西

luogu1231 教辅的组成

最新文章

热门文章
