【题解】 P2763 试题库问题(网络流)

P2763 试题库问题

考虑一个试题要被加入进答案的集合有什么条件？

是某种类型
只算作一次

就这两种且的限制，所以我们用串联的方式连接"类型点"和"作用点"。

判断无解就判断容量是否满了。输出方案就输出有流量的边的终点。

//@winlere

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

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;

}

巴特西

【题解】 P2763 试题库问题(网络流)

P2763 试题库问题

最新文章

热门文章