网络流24题-试题库问题

· · 题解

P2763 试题库问题

题意有点不清

要注意每道题虽可以有多种类型，但却只能与一种类型相匹配

即最后输出时不能在不同种类型中出现同一道题

理解了题意后显然是要我们求某种题与类型之间的的匹配

而类型可以匹配多道题，而且要求某个类型只能匹配特定数量的题

故将类型（n+i）作为右部，与汇点t连容量为题目给出的匹配数量的边

求完最大流后这些边是否满流自然就意味着是否有解

题与类型之间也根据题的类型连边，每道题最多只能有1的贡献，故容量为1

再将源点s与各道题连边，求最大流

如上所述，若最大流不等于m则无解

若相等，则从1到k遍历所有右部点（类型），对每个右部点遍历邻接点，将所有值为1（这个别忘了），且指向左部的边指向的点输出即可

（喜欢就给个赞顶顶我吧）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=1000+5,K=20+5;
const int inf=0x7fffffff;
template<class T>inline void read(T &num){
    char ch;
    while(!isdigit(ch=getchar()));
    num=ch-'0';
    while(isdigit(ch=getchar()))num=num*10+ch-'0';
}
int hea[N<<1],to[N*N<<1],nex[N*N<<1],val[N*N<<1],tot=1,n,k,dep[N<<1],s,t,m;

inline void add_edge(const int x,const int y,const int w){
    to[++tot]=y,nex[tot]=hea[x],hea[x]=tot,val[tot]=w;
}

inline void Add_edge(const int x,const int y,const int w){
//printf("%d --> %d ( %d )\n",x,y,w);
    add_edge(x,y,w);
    add_edge(y,x,0);
}

queue<int> que;
bool bfs(){
    memset(dep,0,sizeof(dep));
    dep[s]=1; 
    while(que.size())que.pop();
    que.push(s);
    int x;
    while(que.size()){
        x=que.front();que.pop();
        for(int i=hea[x];i;i=nex[i]){
            int y=to[i];
            if(val[i]&&!dep[y]){
                dep[y]=dep[x]+1;
                if(y==t)return true;
                que.push(y);
            }
        }
    }
    return false;
}

int dfs(const int x,const int flow){
//printf("dfs(%d,%d) %d\n",x,flow,x==t);
    if(x==t)return flow;
    int rest=flow,k;
    for(int i=hea[x];i&&rest;i=nex[i]){
        int y=to[i];
        if(val[i]&&dep[y]==dep[x]+1){
            k=dfs(y,min(rest,val[i]));
            if(k){
                val[i]-=k;
                val[i^1]+=k;
                rest-=k;
            }
            else dep[y]=0;
        }
    }
//printf("\t%d x=%d,return %d\n",x==s,x,flow-rest);
    return flow-rest;
}

int dinic(){
    int maxflow=0,flow;
    while(bfs())while(flow=dfs(s,inf))maxflow+=flow;
//printf("return %d\n",maxflow);
    return maxflow;
}

inline void print(const int x){
    for(int i=hea[x];i;i=nex[i]){
        int y=to[i];
//printf("\ny=%d\n",y);
        if(val[i]&&y<=n){
            printf(" %d",y);
        }
    }
}

int main(){
    read(k),read(n);
    s=n+k+1;
    t=s+1;
    for(int i=1,w;i<=k;++i){
        read(w);
        m+=w;
        Add_edge(n+i,t,w);
    }
    for(int i=1,b,h;i<=n;++i){
        Add_edge(s,i,1);
        read(h);
        for(int j=1;j<=h;++j){
            read(b);
            Add_edge(i,b+n,1);
        }
    }
    if(dinic()==m){
        for(int i=1;i<=k;++i){
            printf("%d:",i); 
            print(n+i);
            putchar('\n');
        }
    }
    else{
        printf("No Solution!\n");
    }
    return 0;
}