这个题和那个圆桌聚餐很像。

不过注意一点，一个题如果有多种类型，那么那个题最后只能归结到一种题型中。有些同学可能就因此怀疑样例（尽管有SPJ）。

所以最后的建图就是这样：从[tex]S[/tex]向所有题目结点连一条容量为1的边，每个题目向对应题型连一条容量为1的边，每个题型向[tex]T[/tex]连一条容量为该类型题目需要数量的边。跑一遍最大流即可，当且仅当最大流为[tex]m[/tex]时有解。

输出解吧其实也不难，直接判断从题目结点出发的弧是否满载即可。注意不要把反向弧和普通弧弄混。

代码：

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=1030,maxk=25;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
 
struct Edge{
    int u,v,cap,flow;
};
namespace Dinic{
    vector<Edge> edges;
    vector<int> G[maxn];
    int m;
    inline void AddEdge(int u,int v,int cap){
        edges.push_back((Edge){u,v,cap,0});
        edges.push_back((Edge){v,u,0,0});
        m=edges.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
    }
    bool vis[maxn];
    int d[maxn],cur[maxn];
    int s,t;
    inline bool BFS(){
        register int i,u;
        queue<int> Q;
        CL_ARR(vis,0);
        Q.push(s);
        d[s]=0;
        vis[s]=true;
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            REP(i,G[u].size()){
                Edge& e=edges[G[u][i]];
                if(!vis[e.v] && e.cap>e.flow){
                    vis[e.v]=1;
                    d[e.v]=d[u]+1;
                    Q.push(e.v);
                }
            }
        }
        return vis[t];
    }
    int DFS(int x,int a){
        if(x==t || a==0)
            return a;
        int flow=0,temp;
        for(int& i=cur[x];i<G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if(d[e.v]==d[x]+1){
                temp=DFS(e.v,min(a,e.cap-e.flow));
                if(temp>0){
                    e.flow+=temp;
                    edges[G[x][i]^1].flow-=temp;
                    flow+=temp;
                    a-=temp;
                    if(a==0)
                        break;
                }
            }
        }
        return flow;
    }
    inline int Maxflow(int S,int T){
        s=S;
        t=T;
        register int ans=0;
        while(BFS()){
            CL_ARR(cur,0);
            ans+=DFS(s,0x7f7f7f7f);
        }
        return ans;
    }
};

vector<int> ans[maxn];
int main(){
	int k,n,u,p;
	register int i,j,m=0,flow;
	freopen("testlib.in","r",stdin);
	freopen("testlib.out","w+",stdout);
	scanf("%d%d",&k,&n);
	REP_B(i,k){
		scanf("%d",&u);
		m+=u;
		Dinic::AddEdge(i+n,k+n+1,u);
	}
	REP_B(i,n){
		scanf("%d",&p);
		Dinic::AddEdge(0,i,1);
		REP_B(j,p){
			scanf("%d",&u);
			Dinic::AddEdge(i,n+u,1);
		}
	}
	flow=Dinic::Maxflow(0,n+k+1);
	if(flow!=m){
		puts("NoSolution!");
		return 0;
	}
	REP_B(i,n){
		for(j=0;j<Dinic::G[i].size();j++){
			Edge& e=Dinic::edges[Dinic::G[i][j]];
			if(e.v>n && e.v<=(n+k) && e.cap==e.flow){
				ans[e.v-n].push_back(i);
			}
		}
	}
	REP_B(i,k){
		printf("%d:",i);
		REP(j,ans[i].size()){
			printf(" %d",ans[i][j]);
		}
		putchar('\n');
	}
	return 0;
}

• 相关文章
• 全局相关文章