试题库问题

题目链接
咕咕咕咕咕咕二个半月。。。。
给k个题目类型和n个题目,然后要求组成一套有\(a_i\)个i类试题的试卷,每个题目可以对应p类题目,但是只能作为一类使用,求组出的题目。
源点往题目连边1,题目往类型连边1,类型往汇点连需要个数,最大流。


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const ll MAXN = 6000;
const ll maxm = 300000;
struct Edge{
	ll from, to, cap, flow;
	Edge(){
	}
	Edge(ll from, ll to, ll cap, ll flow):from(from), to(to), cap(cap), flow(flow){}	
};
struct Edge1
{
    ll from, to; ll dist;       
    Edge1(ll from, ll to, ll dist):from(from), to(to), dist(dist) {}
};
struct Dinic{
	ll n, m, s, t;
	vector<Edge>edges;
	vector<ll>G[MAXN];
	ll d[MAXN];
	ll cur[MAXN];
	ll vis[MAXN];
	void init(ll n, ll s, ll t)
	{
		this->n = n;this->s = s;this->t = t;
		edges.clear();
		for(ll i = 0;i <= n;++i) G[i].clear();
	}
	
	void add_edge(ll from, ll to, ll cap)
	{
		edges.push_back( Edge(from, to, cap, 0) );
		edges.push_back( Edge(to, from, 0, 0) );
		m = edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1); 
	}
	
	bool bfs(){
		memset(vis, 0, sizeof(vis));
		queue<ll>Q;
		Q.push(s);
		d[s] = 0;
		vis[s] = true;
		while(!Q.empty())
		{
			ll x = Q.front();
			Q.pop();
			for(ll i = 0;i < G[x].size();++i)
			{
				Edge& e = edges[G[x][i]];
				if(!vis[e.to] && e.cap > e.flow)
				{
					vis[e.to] = true;
					d[e.to] = d[x] + 1;
					Q.push(e.to);
				}
			}		
		}
		return vis[t];
	}
	ll dfs(ll x,ll a)
	{
		if(x == t || a == 0)return a;
		ll flow = 0, f;
		for(ll& i = cur[x];i < G[x].size();++i)
		{
			Edge& e = edges[G[x][i]];
			if(d[x] + 1 == d[e.to] && (f = dfs( e.to, min(a, e.cap-e.flow)))>0)
			{
				e.flow += f;
				edges[G[x][i]^1].flow -= f;
				flow += f;
				a -= f;
				if(a == 0)break; 
			}
		}
		return flow;
	}
	ll maxflow()
	{
		ll flow = 0;
		while(bfs())
		{
			memset(cur, 0, sizeof(cur));
			flow += dfs(s,inf);
		}
		return flow;
	}
}gao;
int main()
{
	int n,k;
	scanf("%d%d",&k,&n);
	int S=n+k+1;
	int T=n+k+2;
	int sum=0;
	gao.init(n+k+2,S,T);
	for(int i=1;i<=k;i++){
		int x;
		scanf("%d",&x);
		sum+=x;
		gao.add_edge(n+i,T,x);
	}
	for(int i=1;i<=n;i++){
		gao.add_edge(S,i,1);
		int x;
		scanf("%d",&x);
		for(int j=1;j<=x;j++){
			int y;
			scanf("%d",&y);
			gao.add_edge(i,n+y,1);
		}
	}
	int ans=gao.maxflow();
	vector<int>v[20];
	if(ans!=sum){
		printf("No Solution!\n");
		return 0;
	}else{
		for(int i=0;i<gao.edges.size();i++){
			Edge x=gao.edges[i];
			if(x.from>=1&&x.from<=n&&x.to>n&&x.to<S&&x.flow==1){
				//printf("%lld %lld\n",x.from,x.to);
				v[x.to-n].push_back(x.from);
			}
		}
	}
	for(int i=1;i<=k;i++){
		printf("%d: ",i);
		for(int j=0;j<v[i].size();j++){
			printf("%d ",v[i][j]);
		}
		printf("\n");
	}
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注