POJ 1149 PIGS 【网络流建模汇总】最大流

《网络流建模汇总》最大流专题

对于每个顾客和每个猪圈的分析：

首先求最大，很明显是求最大的流量，那么需要添加源点s和汇点t

和汇点t相连的很明显：每个顾客的最大购买量buy【i】

那么猪圈这个应该怎么转移呢？

题目中的意思是：如果我打开了1，2，3，4这几个猪圈，那么每个都可以互相转化（边的权值为INF）

因为现在网络流中的点是顾客

那么需要建立顾客与顾客的关系：那么只能以猪圈的打开和关闭来连边

如果我是当前打开某个猪圈的第一个顾客：我可以买完所有的~~~那就是看当前猪圈的容量，也就是建立边s-i，边权为猪圈的猪的数量

如果我是后面的第i个顾客：

我可以买完所有的（剩下的），那就是流过来剩下多少是多少，我已经管不了了

那么，我可以限制剩下的：如果我后面还有第i+1个顾客，那么连边i->i+1，表明剩下的都可以转移过去

代码如下：

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<stdio.h>
#include<cstring>
#include<string.h>
using namespace std;

const int maxm=1050;
const int maxn=150;
const int INF=0x3f3f3f3f;
int s,t,tot;
int n,m;
int p[maxm];
int vis[maxm];

struct Edge{
    int to,nxt,cap,flow;
}edge[maxm*10];
int tol,Head[maxm*10];

void init(){
    memset(Head,-1,sizeof(Head));
    tol=2;s=0;t=n+1;tot=t+1;
}

void addedge(int u,int v,int w,int rw=0){
    edge[tol].to=v;
    edge[tol].cap=w;
    edge[tol].flow=0;
    edge[tol].nxt=Head[u];
    Head[u]=tol++;

    edge[tol].to=u;
    edge[tol].cap=rw;
    edge[tol].flow=0;
    edge[tol].nxt=Head[v];
    Head[v]=tol++;
}

int Q[maxn*10],dep[maxn*10],cur[maxn*10],sta[maxn*10];

bool bfs(int s,int t,int n){
    int Front=0,Tail=0;
    memset(dep,-1,sizeof(dep[0])*(n+1));
    dep[s]=0;
    Q[Tail++]=s;
    while(Front<Tail){
        int u=Q[Front++];
        for(int i=Head[u];i!=-1;i=edge[i].nxt){
            int v=edge[i].to;
            if (edge[i].cap>edge[i].flow&&dep[v]==-1){
                dep[v]=dep[u]+1;
                if (v==t) return true;
                Q[Tail++]=v;
            }
        }
    }
    return false;
}

int dinic(int s,int t,int n){
    int maxflow=0;
    while(bfs(s,t,n)){
        for(int i=0;i<n;i++) cur[i]=Head[i];
        int u=s,tail=0;
        while(cur[s]!=-1){
            if (u==t){
                int tp=INF;
                for(int i=tail-1;i>=0;i--)
                    tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
                maxflow+=tp;
                for(int i=tail-1;i>=0;i--){
                    edge[sta[i]].flow+=tp;
                    edge[sta[i]^1].flow-=tp;
                    if (edge[sta[i]].cap==edge[sta[i]].flow) tail=i;
                }
                u=edge[sta[tail]^1].to;
            }
            else if (cur[u]!=-1&&edge[cur[u]].cap>edge[cur[u]].flow&&dep[u]+1==dep[edge[cur[u]].to]){
                sta[tail++]=cur[u];
                u=edge[cur[u]].to;
            }
            else{
                while(u!=s&&cur[u]==-1) u=edge[sta[--tail]^1].to;
                cur[u]=edge[cur[u]].nxt;
            }
        }
    }
    return maxflow;
}

int main(){
    //freopen("input.txt","r",stdin);
    int u,v;
    while(scanf("%d%d",&m,&n)!=EOF){
        for(int i=1;i<=m;i++) scanf("%d",&p[i]);
        init();
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++){
            scanf("%d",&u);
            while(u--){
                scanf("%d",&v);
                if (vis[v])
                    addedge(vis[v],i,INF);
                else
                    addedge(vis[v],i,p[v]);
                vis[v]=i;
            }
            scanf("%d",&u);
            addedge(i,t,u);
        }
        printf("%d\n",dinic(s,t,tot));
    }
    return 0;
}