POJ1149(网络流)

题意：有M个猪圈和N个顾客，最初猪圈是锁着的。每个顾客有其中的A把钥匙，需要买B头猪，顾客在买完猪便将门锁上，而且顾客是按照顺序来的。商家可以对开着的猪圈里面的猪进行任意调配，问最多可以卖出几头猪。

构图：若该顾客是第一个来这个猪圈，则源向这个点连容量为猪圈猪数的边，否则从第一个来这个猪圈的顾客向他连容量无穷大的边，最大流。

参考上交某退役神牛的文献:http://imlazy.ycool.com/post.2059102.html

/*Source Code

Problem: 1149  User: HEU_daoguang
Memory: 712K  Time: 32MS
Language: G++  Result: Accepted

Source Code*/
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
int m,n,a,b,key;
struct Pig{
    int num,first;
}p[1050];

#define V 105
#define E 10500
#define inf 0xffff
struct Edge{
    int u,v,c,next;
}edge[E];
int cnt;
int dist[V];
int head[V];
int que[V];
int sta[V];

void init(){
    cnt=0;
    memset(head,-1,sizeof(head));
}

void addedge(int u,int v,int c){
    edge[cnt].u=u;edge[cnt].v=v;edge[cnt].c=c;
    edge[cnt].next=head[u];head[u]=cnt++;
    edge[cnt].u=v;edge[cnt].v=u;edge[cnt].c=0;
    edge[cnt].next=head[v];head[v]=cnt++;
}

int dinic(int s,int t){
    int ans=0;
    while(true){

        int left,right,u,v;
        memset(dist,-1,sizeof(dist));
        left=right=0;
        que[right++]=s;
        dist[s]=0;

        while(left<right){
            u=que[left++];
            for(int k=head[u];k!=-1;k=edge[k].next){
                u=edge[k].u;
                v=edge[k].v;
                if(edge[k].c>0 && dist[v]==-1){
                    dist[v]=dist[u]+1;
                    que[right++]=v;

                    if(v==t){
                        left=right;
                        break;
                    }
                }
            }

        }

        if(dist[t]==-1) break;

        int top=0;
        int now=s;
        while(true){
            if(now!=t){
                int k;
                for(k=head[now];k!=-1;k=edge[k].next){
                    if(edge[k].c>0 && dist[edge[k].v]==dist[edge[k].u]+1) break;
                }
                if(k!=-1){
                    sta[top++]=k;
                    now=edge[k].v;
                }
                else{
                    if(top==0) break;
                    dist[edge[sta[--top]].v]=-1;
                    now=edge[sta[top]].u;
                }
            }
            else{
                int flow=inf,ebreak;
                for(int i=0;i<top;i++){
                    if(flow>edge[sta[i]].c){
                        flow=edge[sta[i]].c;
                        ebreak=i;
                    }
                }
                ans+=flow;
                for(int i=0;i<top;i++){
                    edge[sta[i]].c-=flow;
                    edge[sta[i]^1].c+=flow;
                }
                now=edge[sta[ebreak]].u;
                top=ebreak;
            }
        }

    }
    return ans;
}

int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d",&m,&n)!=EOF){
        for(int i=1;i<=m;i++){
            scanf("%d",&p[i].num);
            p[i].first=0;
        }
        init();
        for(int i=1;i<=n;i++){
            scanf("%d",&a);
            for(int j=1;j<=a;j++){
                scanf("%d",&key);
                if(p[key].first==0){
                    addedge(0,i,p[key].num);
                    p[key].first=i;
                }
                else{
                    addedge(p[key].first,i,inf);
                }
            }
            scanf("%d",&b);
            addedge(i,n+1,b);
        }
        printf("%d\n",dinic(0,n+1));
    }
    return 0;
}

卡了两点:1.在dfs找增广路中最小权值边时，模板打错了，没有在dfs栈中找，导致“黑洞”。 2.忘初始化了，导致"黑洞"。

通过神牛的文献中学习到了一些建图及优化的思路：

“在面对网络流问题时，如果一时想不出很好的构图方法，不如先构造一个最直观，或者说最“硬来”的模型，然后再用合并节点和边的方法来简直化这个模型。经过简化以后，好的构图思路自然就会涌现出来了。这是解决网络流问题的一个好方法。”