圆桌问题

有m个单位,每个单位有\(r_i\)个人,要分配到n张桌子,每个桌子可以容纳\(c_i\)的人,要求相同单位的人不能同一张桌子上,问能否分配及分配方法。
解 很显然的一道网络流,源点往单位建单位人数的边,桌子往汇点建容纳人数的边,每个单位向每个桌子建流量为1的边,这样可以保证每个单位最多只有1个人在每张桌子上,跑最大流即可。


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const ll MAXN = 1000;
const ll maxm = 100000;
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;//刘汝佳网络流dinic板子
int main()
{
	int m,n;
	scanf("%d%d",&m,&n);
	gao.init(n+m+2,n+m+1,n+m+2);
	int sum=0;
	for(int i=1;i<=m;i++){
		int x;
		scanf("%d",&x);
		sum+=x;
		gao.add_edge(n+m+1,i,x);
	}
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		gao.add_edge(m+i,n+m+2,x);
	}
	for(int i=1;i<=m;i++){
		for(int j=m+1;j<=n+m;j++){
			gao.add_edge(i,j,1);
		}
	}
	set<int>s[155];
	if(sum==gao.maxflow()){
		printf("1\n");
		for(int i=0;i<gao.edges.size();i++){
			Edge k=gao.edges[i];
			if(k.from!=n+m+1&&k.to!=n+m+2&&k.flow==1){
				s[k.from].insert(k.to-m);
			}
		}
		for(int i=1;i<=m;i++){
			for(auto j:s[i]){
				printf("%d ",j);
			}
			printf("\n");
		}
	}else{
		printf("0\n");
	}
}

 

发表评论

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