这个题是经典的网络流题目。在经过一次次的思想过滤后你会发现，这个问题的瓶颈（换猪）大可以理解为前面的顾客给后面的留一些不是？这样问题就简单多了。

按顺序整理出到访每个猪圈的顾客，对于到访每个猪圈的第一个顾客，从[tex]S[/tex]向其连一条容量为此猪圈中猪的数量的边。然后每个猪圈前面一个顾客要个给后面的留一些猪，这个可以直接连一条容量为无限大的边来表示。

最后每个顾客向[tex]T[/tex]连一条容量为其买猪数量上限的边，然后求一遍[tex]S[/tex]到[tex]T[/tex]的最大流，问题得解。

这个题还有一个优化就是，有一些边是可以合并的（比如说从[tex]S[/tex]流出的一些边是可能指向同一顾客的，同一对顾客之间的连边数可能不止1条），但是我没有做这个优化，照样A了……

代码：

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using std::vector;
using std::queue;
using std::min;
const int maxn=105,maxm=1005;
namespace Dinic{
	struct Edge{
		int u,v,cap,flow;
	};
	vector<Edge> edges;
	vector<int> G[maxn];
	int s,t;
	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];
	inline bool bfs(){
		register int i,u,siz;
		queue<int> Q;
		memset(vis,0,sizeof(vis));
		d[s]=0;
		Q.push(s);
		vis[s]=true;
		while(!Q.empty()){
			u=Q.front();Q.pop();
			siz=G[u].size();
			for(i=0;i<siz;i++){
				Edge& e=edges[G[u][i]];
				if(!vis[e.v] && e.cap>e.flow){
					d[e.v]=d[u]+1;
					Q.push(e.v);
					vis[e.v]=true;
				}
			}
		}
		return vis[t];
	}
	int cur[maxn];
	int dfs(int x,int a){
		if(x==t || a==0){
			return a;
		}
		int f,flow=0,siz=G[x].size();
		for(int& i=cur[x];i<siz;i++){
			Edge& e=edges[G[x][i]];
			if(d[e.v]==d[x]+1){
				f=dfs(e.v,min(a,e.cap-e.flow));
				if(f>0){
					flow+=f;
					e.flow+=f;
					edges[G[x][i]^1].flow-=f;
					a-=f;
					if(a==0){
						break;
					}
				}
			}
		}
		if(a>0){
			d[x]=-1;
		}
		return flow;
	}
	inline int solve(int S,int T){
		register int ans=0;
		s=S;t=T;
		while(bfs()){
			memset(cur,0,sizeof(cur));
			ans+=dfs(s,0x7fffffff);
		}
		return ans;
	}
};
using Dinic::AddEdge;
using Dinic::solve;
int pigs[maxm];
vector<int> Use[maxm];
int main(){
	register int i,j;
	int m,n;
	scanf("%d%d",&m,&n);
	for(i=1;i<=m;i++){
		scanf("%d",&pigs[i]);
	}
	for(i=1;i<=n;i++){
		int a,b,temp;
		scanf("%d",&a);
		for(j=1;j<=a;j++){
			scanf("%d",&temp);
			Use[temp].push_back(i);
		}
		scanf("%d",&b);
		AddEdge(i,n+1,b);
	}
	for(i=1;i<=m;i++){
		AddEdge(0,Use[i][0],pigs[i]);
		int siz=Use[i].size();
		for(j=1;j<siz;j++){
			AddEdge(Use[i][j-1],Use[i][j],0x7f7f7f7f);
		}
	}
	printf("%d\n",solve(0,n+1));
	return 0;
}

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