1，從各個顧客到匯點各有一條邊，容量就是各個顧客能買的數(shù)量上限。

2，在某一輪中，從該顧客打開的所有豬圈都有一條邊連向該顧客，容量都是∞。

3，最后一輪除外，從每一輪的i號豬圈都有一條邊連向下一輪的i號豬圈，容量都是∞，表示這一輪剩下的豬可以留到下一輪。

4，最后一輪除外，從每一輪被打開的所有豬圈，到下一輪的同樣這些豬圈，兩兩之間都要連一條邊，表示它們之間可以任意流通。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int inf=0x3f3f3f3f;struct node{int v,w,nextt;
}e[100005];
int head[105],deep[105],cur[105];
int a[1005],sign[1005];
vector<int>b[105];
int s,t,tot;
inline int read(){int sum=0,x=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')x=0;ch=getchar();}while(ch>='0'&&ch<='9')sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar();return x?sum:-sum;
}
inline void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');
}
void addedge(int u,int v,int w){e[tot].v=v;e[tot].w=w;e[tot].nextt=head[u];head[u]=tot++;e[tot].v=u;e[tot].w=0;e[tot].nextt=head[v];head[v]=tot++;}
bool bfs(){for(int i=0;i<=t;i++)deep[i]=0;queue<int>que;que.push(s);deep[s]=1;while(!que.empty()){int u=que.front();que.pop();for(int i=head[u];~i;i=e[i].nextt){int v=e[i].v;if(e[i].w>0&&deep[v]==0){deep[v]=deep[u]+1;if(v==t)return true;que.push(v);}}}return deep[t]==0?false:true;
}
int dfs(int u,int fl){if(u==t)return fl;int x,ans=0;for(int i=cur[u];~i;i=e[i].nextt){int v=e[i].v;if(e[i].w>0&&deep[v]==deep[u]+1){x=dfs(v,min(fl-ans,e[i].w));ans+=x;e[i].w-=x;e[i^1].w+=x;if(e[i].w)cur[u]=1;if(ans==fl)return fl;}}if(ans==0)deep[u]=0;return ans;
}
int dinic(int n){int ans=0;while(bfs()){for(int i=0;i<=n;i++)cur[i]=head[i];ans+=dfs(s,inf);}return ans;
}
void init(int n){s=0,t=n+1;memset(head,-1,sizeof(head));
}
int main(){int m=read(),n=read();init(n);for(int i=1;i<=m;i++)a[i]=read();for(int i=1;i<=n;i++){int x=read(),y;while(x--){y=read();b[i].push_back(y);}y=read();addedge(i,t,y);}for(int i=1;i<=n;i++){for(int j=0;j<b[i].size();j++){int v=b[i][j];if(!sign[v]){sign[v]=i;addedge(s,i,a[v]);}else{addedge(sign[v],i,inf);sign[v]=i;}}}write(dinic(t));putchar('\n');return 0;
}

View Code

?

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

總結(jié)

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

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