lp2763 网络流24题-试题库问题

对于这一题，我们建三层的边来描述题目中的约束。
对于每道题建一个点，源点连一条容量为1的边到每一个点，表示每道题最多只能被选取一次。
对于每个种类建一个点，每一个点连一条容量为1的边到它所属的所有类，表示它仅可以被作为这个类来选取。
每个种类连一条容量为这个种类需要的选取次数的边到汇点，表示这个种类最多需要被选取的次数。
然后，跑一遍当前弧优化Dinic最大流，如果需要选取的总题数都能选取到，流量就等于需要选取的总题数。
当然也可以大力拆点跑二分图匹配，不过那样似乎更难写的样子。

#include<iostream>
#include<cstdio>
#include<queue>
const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[40005];
int h[2005],et=-1;
int dep[2005],nw[2005];

inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}

inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0); 
}

int n,m,s,t,Sans=0,tot; 

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF;
		nw[i]=h[i];
	}
	while(!q.empty()){
		q.pop();
	}
	dep[s]=0;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
	return dep[t]<INF;
} 
//V表示从源点到当前路径上的剩余流量，cnt表示这个点向后流了多少流量。 
inline int dfs(int X,int V){
	if(V<=0||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(V,e[i].w));
			if(val){
				cnt+=val;
				e[i].w-=val;
				e[i^1].w+=val;
				V-=val;
				if(V<=0){
					break;
				}
			}
		}
	}
	return cnt;
}

void init(){
	scanf("%d%d",&m,&n);
	s=m+n+1,t=m+n+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
//	注意初始化。 
	int p,x;
	for(int i=1;i<=m;++i){
		scanf("%d",&x);
		Sans+=x;
		add(n+i,t,x);
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&p);
		add(s,i,1);
		for(int j=1;j<=p;++j){
			scanf("%d",&x);
			add(i,n+x,1);
//			注意哈希。 
		}
	}
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
		printf("%d\n",ans); 
	}
	if(ans<Sans){
		puts("No solution!");
		return;
	}
	for(int i=1;i<=m;++i){
		printf("%d: ",i);
		for(int j=h[n+i];j;j=e[j].nxt){
			if((j&1)&&(e[j].w==1)&&(e[j].v!=t)){
				printf("%d ",e[j].v);
			}
		}
		puts("");
	}
}

int main(){
	init();
	return 0;
}