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

传送门

解题思路

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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>

using namespace std;
const int MAXN = 2005;
const int MAXM = 50005;
const int inf = 0x3f3f3f3f;

inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f?x:-x;
}

int k,n,head[MAXN],cnt=1,d[MAXN],sum,Sum;
int S=0,T=2000,to[MAXM<<1],nxt[MAXM<<1],val[MAXM<<1];
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,0,sizeof(d));
    d[S]=1;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]+1;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]+1 && val[i]){
            k=dinic(u,min(flow,val[i]));
            if(!k) d[u]=0;
            val[i]-=k;val[i^1]+=k;res-=k;
        }
    }
    return flow-res;
}

int main(){
    k=rd(),n=rd();int x,y;
    for(int i=1;i<=k;i++)
        x=rd(),add(i,T,x),add(T,i,0),Sum+=x; 
    for(int i=1;i<=n;i++){
        x=rd();
        for(int j=1;j<=x;++j){
            y=rd();add(i+k,y,1);add(y,i+k,0);
        }
    }
    for(int i=1;i<=n;i++) add(S,i+k,1),add(i+k,S,0);
    while(bfs()) sum+=dinic(S,inf);
//    cout<<sum<<endl;
    for(int i=1;i<=k;i++)
        for(int j=head[i];j;j=nxt[j]){
            if(to[j]==T) continue;
            if(!val[j^1]) ans[i].push_back(to[j]-k);
        }
    for(int i=1;i<=k;i++){
        printf("%d: ",i);
        for(int j=0;j<ans[i].size();j++) printf("%d ",ans[i][j]);
        printf("
");
    }
    return 0;
}