P2763 试题库问题 (网络流 最大流)

传送门

解题思路

比较简单的网络流，建图还是比较好想的。让源点向试题连流量为1的边，试题向所属类型连流量为1的边，类型向汇点连流量为需要此类试题的边。直接跑最大流，输出答案时找到那些满流的边所对的点。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<vector>

using namespace std;

const int MAXN = ;

const int MAXM = ;

const int inf = 0x3f3f3f3f;

inline int rd(){

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)) {f=ch=='-'?:;ch=getchar();}

    while(isdigit(ch))  {x=(x<<)+(x<<)+ch-'';ch=getchar();}

    return f?x:-x;

}

int k,n,head[MAXN],cnt=,d[MAXN],sum,Sum;

int S=,T=,to[MAXM<<],nxt[MAXM<<],val[MAXM<<];

queue<int> Q;vector<int> ans[MAXN];

inline void add(int bg,int ed,int w){

    to[++cnt]=ed,nxt[cnt]=head[bg],val[cnt]=w,head[bg]=cnt;

}

bool bfs(){

    while(Q.size()) Q.pop();memset(d,,sizeof(d));

    d[S]=;Q.push(S);

    while(!Q.empty()){

        int x=Q.front();Q.pop();

        for(register int i=head[x];i;i=nxt[i]){

            int u=to[i];

            if(!d[u] && val[i]) {

                d[u]=d[x]+;Q.push(u);

                if(u==T) return true;

            }

        }

    }

    return false;

}

int dinic(int x,int flow){

    if(x==T) return flow;

    int res=flow,k;

    for(register int i=head[x];i && res;i=nxt[i]){

        int u=to[i];

        if(d[u]==d[x]+ && val[i]){

            k=dinic(u,min(flow,val[i]));

            if(!k) d[u]=;

            val[i]-=k;val[i^]+=k;res-=k;

        }

    }

    return flow-res;

}

int main(){

    k=rd(),n=rd();int x,y;

    for(int i=;i<=k;i++)

        x=rd(),add(i,T,x),add(T,i,),Sum+=x;

    for(int i=;i<=n;i++){

        x=rd();

        for(int j=;j<=x;++j){

            y=rd();add(i+k,y,);add(y,i+k,);

        }

    }

    for(int i=;i<=n;i++) add(S,i+k,),add(i+k,S,);

    while(bfs()) sum+=dinic(S,inf);

//    cout<<sum<<endl;

    for(int i=;i<=k;i++)

        for(int j=head[i];j;j=nxt[j]){

            if(to[j]==T) continue;

            if(!val[j^]) ans[i].push_back(to[j]-k);

        }

    for(int i=;i<=k;i++){

        printf("%d: ",i);

        for(int j=;j<ans[i].size();j++) printf("%d ",ans[i][j]);

        printf("\n");

    }

    return ;

}