POJ1149-PIGS

1，从各个顾客到汇点各有一条边，容量就是各个顾客能买的数量上限。

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('
');
    return 0;
}