P2763 试题库问题
考虑一个试题要被加入进答案的集合有什么条件？
- 是某种类型
- 只算作一次
就这两种且的限制，所以我们用串联的方式连接"类型点"和"作用点"。
判断无解就判断容量是否满了。输出方案就输出有流量的边的终点。
//@winlere#include#include #include #include #include using namespace std; typedef long long ll;inline int qr(){ register int ret=0,f=0; register char c=getchar(); while(c<48||c>57)f|=c==45,c=getchar(); while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar(); return f?-ret:ret;}const int inf=0x3f3f3f3f;const int maxn=1.9e3+5;int nodecnt;struct E{ int to,nx,w;}e[50005];int head[maxn];int cur[maxn];int d[maxn];int cnt=-1,S,T,n,m,k;vector< int > ve[maxn];inline void add(const int&fr,const int&to,const int&w,const int&f){ //printf("fr=%d to=%d w=%d cnt=%d\n",fr,to,w,cnt); e[++cnt]={to,head[fr],w}; head[fr]=cnt; if(f)add(to,fr,0,0);}queue< int >q;inline bool bfs(){ for(register int t=1;t<=n+k+2;++t) cur[t]=head[t],d[t]=0; q.push(S); d[S]=1; while(!q.empty()){ register int now=q.front(); q.pop(); if(now==T)continue; for(register int t=head[now];t!=-1;t=e[t].nx){ if(!d[e[t].to]&&e[t].w>0){ d[e[t].to]=d[now]+1; q.push(e[t].to); } } } return d[T];}int dfs(const int&now,const int&last,int fl){ if(now==T||fl==0)return fl; register int ret=0; for(register int&t=cur[now];t!=-1;t=e[t].nx){ if(e[t].w>0&&d[e[t].to]==d[now]+1&&fl){ int d=dfs(e[t].to,now,min(fl,e[t].w)); e[t].w-=d;e[t^1].w+=d;ret+=d;fl-=d; } } return ret;}inline int dinic(){ register int ret=0; while(bfs()) ret+=dfs(S,0,inf); return ret;}int main(){ freopen("testlib.in","r",stdin); freopen("testlib.out","w",stdout); memset(head,-1,sizeof head); k=qr();n=qr(); S=1;T=k+n+2; for(register int t=1;t<=k;++t) add(S,t+1,qr(),1); for(register int t=1,t1;t<=n;++t){ t1=qr(); for(register int i=1;i<=t1;++i) add(qr()+1,t+k+1,1,1); add(t+k+1,T,1,1); } dinic(); int ok=1; for(register int t=head[S];t!=-1;t=e[t].nx) if(e[t].w) ok=0; if(ok) { //printf("%d\n",f); for(register int now=2;now<=k+1;++now){ printf("i:%d ",now-1); for(register int t=head[now];t!=-1;t=e[t].nx) if(e[t].to!=1&&e[t].w==0) printf("%d ",e[t].to-k-1); putchar('\n'); } } else puts("No Solution!"); return 0;}