建圖：s向所有豬圈的第一個顧客連流量為這個豬圈里住的數(shù)量，然后對于之后每個來這個豬圈的顧客，由他前一個顧客向他連邊權(quán)為無窮的邊，然后每個顧客向t連流量為這個顧客購買上限的邊。然后跑最大流

#include<iostream> #include<cstdio> #include<vector> #include<cstring> #include<queue> using namespace std; const int M=1005,N=105,inf=1e8;; int m,n,a[M],b[N],s,t,h[N],cnt=1,le[N]; vector<int>v[M]; struct qwe {int ne,to,v; }e[N*N<<1]; int read() {int r=0,f=1;char p=getchar();while(p>'9'||p<'0'){if(p=='-')f=-1;p=getchar();}while(p<='9'&&p>='0'){r=r*10+p-48;p=getchar();}return r*f; } void add(int u,int v,int w) {cnt++;e[cnt].ne=h[u];e[cnt].to=v;e[cnt].v=w;h[u]=cnt; } void ins(int u,int v,int w) {add(u,v,w);add(v,u,0); } bool bfs() {queue<int>q;memset(le,0,sizeof(le));q.push(s);le[s]=1;while(!q.empty()){int u=q.front();q.pop();for(int i=h[u];i;i=e[i].ne)if(e[i].v>0&&!le[e[i].to]){le[e[i].to]=le[u]+1;q.push(e[i].to);}}return le[t]; } int dfs(int u,int f) {if(u==t||!f)return f;int us=0;for(int i=h[u];i;i=e[i].ne)if(e[i].v>0&&le[e[i].to]==le[u]+1){int t=dfs(e[i].to,min(e[i].v,f-us));e[i].v-=t;e[i^1].v+=t;us+=t;}if(us==0)le[u]=0;return us; } int dinic() {int re=0;while(bfs())re+=dfs(s,inf);return re; } int main() {m=read(),n=read();s=0,t=n+1;for(int i=1;i<=m;i++)a[i]=read();for(int i=1;i<=n;i++){int x=read();for(int j=1;j<=x;j++){int y=read();v[y].push_back(i);}b[i]=read();ins(i,t,b[i]);}for(int i=1;i<=m;i++)if(v[i].size()){ins(s,v[i][0],a[i]);for(int j=1;j<v[i].size();j++)ins(v[i][j-1],v[i][j],inf);}printf("%d\n",dinic());return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/lokiii/p/8383447.html

總結(jié)

以上是生活随笔為你收集整理的poj 1149 PIGS【最大流】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。