【luogu2763】试题库问题 [网络流 最大流]

[luoguP2763]

就在upd的时候记录一下答案就好啦！
懒得去深究我的玄学REQAQ(好像是有可能e[pre[x]^1].v指向的是其他点？？？但我觉得不可能啊...

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<stack>
using namespace std;
#define Min(x,y) ((x)<(y)?(x):(y))
const int N=5000+50,M=30000+5,inf=0x3f3f3f3f,P=19650827;
int k,n,m,s,t,tt,nw=0,ans[3000][1500],a[N],incf[N],pre[N];
template <class t>void rd(t &x){
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}

int head[N],tot=1;
struct edge{int v,flo,nxt;}e[M<<1];
void add(int u,int v,int flo){
	e[++tot]=(edge){v,flo,head[u]},head[u]=tot;
	e[++tot]=(edge){u,0,head[v]},head[v]=tot;
}

queue<int>q;bool vis[N];
bool bfs(){
	while(!q.empty()) q.pop();
	memset(vis,0,sizeof(vis));
	q.push(s),vis[s]=1,incf[s]=inf;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=head[u],v;i;i=e[i].nxt)
		if(e[i].flo&&!vis[v=e[i].v]){
			incf[v]=Min(incf[u],e[i].flo);
			q.push(v),vis[v]=1,pre[v]=i;
			if(v==t) return 1;
		}
	}
	return 0;
}
void upd(){
	int x=t;
	while(x!=s){
		int i=pre[x];
		e[i].flo-=incf[t],e[i^1].flo+=incf[t];
		if(k<x<=tt) ans[e[pre[x]^1].v][++ans[e[pre[x]^1].v][0]]=x-k;
		x=e[i^1].v;
	} 
	nw+=incf[t];
}

int main(){
	freopen("in2.txt","r",stdin);
	//freopen("xor.out","w",stdout);
	memset(ans,0,sizeof(ans));
	rd(k),rd(n);tt=n+k,s=n+n+k+1,t=s+1;
	for(int i=1;i<=k;++i) rd(a[i]),m+=a[i];
	for(int i=1;i<=k;++i) add(s,i,a[i]);
	for(int i=1,num,x;i<=n;++i){
		rd(num);
		for(int j=1;j<=num;++j) rd(x),add(x,i+k,1);
	}
	for(int i=1;i<=n;++i) add(i+k,i+tt,1),add(i+tt,t,1);
	while(bfs())
	upd();
	if(nw!=m) return puts("No Solution!"),0;
	for(int i=1;i<=k;++i){
		printf("%d: ",i);
		for(int j=1;j<=a[i];++j) printf("%d ",ans[i][j]);
		puts("");
	}
	return 0;
}