题目大意：有m个猪圈，有n个客户来卖猪，每个人有相应的钥匙，并且买完后可以重新组合新的猪圈，问最后最多可以卖掉多少？
题目解析：因为是有顺序的，所以遍历每个客户所对应的猪圈的时候，如果该猪圈没有被打开过m，就连一条a[i]的边，如果被打开过，就从上一个打开的客户连向这个客户，值为inf，最后每个客户指向汇点即可；
AC代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<queue> using namespace std; const int inf=0x3fffffff; const int maxn=1010; struct node { int to,cap,rev; node(int a,int b,int c) { to=a; cap=b; rev=c; } }; vector<node>vec[maxn]; int pre[maxn],iter[maxn]; bool vis[maxn]; void add_edge(int from,int to,int cost) { vec[from].push_back(node(to,cost,vec[to].size())); vec[to].push_back(node(from,0,vec[from].size()-1)); } void bfs(int s){ memset(pre,-1,sizeof(pre)); queue<int>que; pre[s]=0;que.push(s); while(!que.empty()){ int v=que.front();que.pop(); for(int i=0;i<vec[v].size();i++){ node &e=vec[v][i]; if(e.cap>0&&pre[e.to]<0){ pre[e.to]=pre[v]+1; que.push(e.to); } } } } int dfs(int v,int t,int f){ if(v==t) return f; for(int &i=iter[v];i<vec[v].size();i++){ node &e=vec[v][i]; if(e.cap>0&&pre[v]<pre[e.to]){ int d=dfs(e.to,t,min(f,e.cap)); if(d>0){ e.cap-=d; vec[e.to][e.rev].cap+=d; return d; } } } return 0; } int max_flow(int u,int v) { int flow=0; while(1) { bfs(u); if(pre[v]<0) return flow; memset(iter,0,sizeof(iter)); int f; while((f=dfs(u,v,inf))>0) flow+=f; } } int main() { int n,m,a[1010],t,temp,i,last[1010],u; while(scanf("%d%d",&m,&n)!=EOF) { for(i=0;i<maxn;i++) vec[i].clear(); for(i=1;i<=m;i++) { scanf("%d",&a[i]); } memset(vis,0,sizeof(vis)); for(i=1;i<=n;i++) { scanf("%d",&t); while(t--) { scanf("%d",&u); if(!vis[u]) { vis[u]=1; add_edge(0,i,a[u]); last[u]=i; } else { add_edge(last[u],i,inf); last[u]=i; } } scanf("%d",&t); add_edge(i,n+1,t); } printf("%d\n",max_flow(0,n+1)); } return 0; }
