洛谷 P2763 试题库问题

题目传送门

源点向每个试题连容量为1的边,试题向试题类型连容量为1的边,试题类型向汇点连容量为本类型所需题数的边.跑最大流

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#define pd(i) (i % 2 == 1) ? i + 1 : i - 1 

using namespace std;

int k,n,s,t = 1990,tot,dis[2001],ans,hu[2001],sum;
vector<int> d[2000];
struct kkk {
	int fr,to,ll,rl;
}e[10001];

inline void add(int x,int y,int v) {
	e[++tot].fr = x;
	e[tot].to = y;
	e[tot].rl = v;
	e[tot].ll = 0;
	d[x].push_back(tot);
	e[++tot].fr = y;
	e[tot].to = x;
	e[tot].rl = 0;
	e[tot].ll = 0;
	d[y].push_back(tot);
}

inline bool bfs() {
	memset(dis,-1,sizeof(dis));
	queue<int> q;
	q.push(s);
	dis[s] = 0;
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int i = 0;i < d[u].size(); i++) {
			kkk o = e[d[u][i]];
			if(dis[o.to] == -1 && o.rl > o.ll) {
				dis[o.to] = dis[u] + 1;
				q.push(o.to);
			}
		}
	}
	return dis[t] != -1;
}

inline int dfs(int u,int a) {
	if(u == t || a == 0) return a;
	int _ans = 0;
	for(int &i = hu[u];i < d[u].size(); i++) {
		kkk &o = e[d[u][i]];
		if(dis[o.to] == dis[u] + 1) {
			int f = dfs(o.to,min(a,o.rl - o.ll));
			o.ll += f;
			e[pd(d[u][i])].ll -= f;
			a -= f;
			_ans += f;
			if(a == 0) break;
		}
	}
	return _ans;
}

int main() {
	scanf("%d%d",&k,&n);
	for(int i = 1;i <= k; i++) {
		int u;
		scanf("%d",&u);
		sum += u;
		add(i + n,t,u);
	}
	for(int i = 1;i <= n; i++) {
		int p;
		scanf("%d",&p);
		for(int j = 1;j <= p; j++) {
			int oo;
			scanf("%d",&oo);
			add(i,oo + n,1);
		}
		add(s,i,1);
	}
	while(bfs()) {
		memset(hu,0,sizeof(hu));
		ans += dfs(s,100000);
	}
	if(ans != sum) {
		printf("No Solution!");
		return 0;
	}
	for(int i = 1;i <= k; i++) {
		printf("%d:",i);
		for(int j = 0;j < d[i+n].size(); j++)
			if(e[d[i+n][j]].ll == -1)
				printf("%d ",e[d[i+n][j]].to);
		printf("
");
	}
	return 0;
}