ZOJ - 3229 Shoot the Bullet (有源汇点上下界最大流)

题意:要在n天里给m个女生拍照，每个女生有拍照数量的下限Gi，每天有拍照数量的上限Di，每天当中每个人有拍照的上限Lij和Rij。求在满足限制的基础上，所有人最大能拍多少张照片。

分析:抛开限制，显然是一道最大流的问题，需要新建虚拟源点s和虚拟汇点t。加上上下界限制后就是有源汇点的上下界最大流问题。

要求解这个最大流，首先得保证上下界可行流有解。新增一个超级源点ss,超级汇点tt。点[1,n]视作n天，[n+1,n+m]视作m个女生。由源点s向[1,n]分别建容量为Di的弧，由于下界是0，所以不用分离出来。由[n+1,n+m]向汇点t建容量为INF - Gi的边，表示其下界为Gi,上界为正无穷。对于天数i中女生j的上下界Lij与Rij，从i向j+n建容量为Rij-Lij的弧。

记录每个点（包括s和t）的入流-出流的值cap[i]，若cap[i]>0,由超级源点ss向其建容量为cap[i]；若cap[i]<0,由该点向超级汇点tt建容量为-cap[i]的边。跑出ss到tt的最大流f，若f==由ss出发的所有边的流量上限之和，则说明有可行流。

在确保有可行流的基础上，该题要求的是最大流，做法是在残余网上跑出s到t的最大流，得到的最大流即为所求答案。

本题还需输出代表每天每人拍摄照片数的流量，则该流量 = 该弧流量下界 + 第二次跑出的*流。

#include<bits/stdc++.h>
using namespace std;
using namespace std;
typedef int LL;
const int MAXN = 1505;
const int INF = 0x3f3f3f3f;

struct ISAP{
    int n;//实际建图总点数（最好比图中总点数大一点）
    struct Edge{
        int v,next;
        LL cap,flow;
    }edge[MAXN*100];
    int cur[MAXN],pre[MAXN],gap[MAXN],path[MAXN],dep[MAXN];
    int tot=0;//实际存储总边数
    void init(int n){
        this -> n  =n;
        tot=0;
        memset(pre,-1,sizeof(pre));
    }
    void AddEdge(int u,int v,LL w,LL rw=0)//加边 单向图三个参数  双向图四个
    {
        edge[tot] = (Edge){v,pre[u],w,0};
        pre[u]=tot++;
        edge[tot] = (Edge){u,pre[v],rw,0};
        pre[v]=tot++;
    }
    bool bfs(int s,int t){//其实这个bfs可以融合到下面的迭代里，但是好像是时间要长
        memset(dep,-1,sizeof(dep));
        memset(gap,0,sizeof(gap));
        gap[0]=1;
        dep[t]=0;
        queue<int>q;
        while(!q.empty())
        q.pop();
        q.push(t);//从汇点开始反向建层次图
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=pre[u];i!=-1;i=edge[i].next){
                int v=edge[i].v;
                if(dep[v]==-1&&edge[i^1].cap>edge[i^1].flow)//注意是从汇点反向bfs，但应该判断正向弧的余量
                {
                    dep[v]=dep[u]+1;
                    gap[dep[v]]++;
                    q.push(v);
                    //if(v==s)//感觉这两句优化加了一般没错，但是有的题可能会错，所以还是注释出来，到时候视情况而定
                    //break;
                }
            }
        }
        return dep[s]!=-1;
    }
    LL isap(int s,int t){
        bfs(s,t);
        memcpy(cur,pre,sizeof(pre));
        int u=s;
        path[u]=-1;
        LL ans=0;
        while(dep[s]<n){//迭代寻找增广路
            if(u==t){
                LL f=INF;
                for(int i=path[u];i!=-1;i=path[edge[i^1].v])//修改找到的增广路
                    f=min(f,edge[i].cap-edge[i].flow);
                for(int i=path[u];i!=-1;i=path[edge[i^1].v]){
                    edge[i].flow+=f;
                    edge[i^1].flow-=f;
                }
                ans+=f;
                u=s;
                continue;
            }
            bool flag=false;
            int v;
            for(int i=cur[u];i!=-1;i=edge[i].next){
                v=edge[i].v;
                if(dep[v]+1==dep[u]&&edge[i].cap-edge[i].flow){
                    cur[u]=path[v]=i;//当前弧优化
                    flag=true;
                    break;
                }
            }
            if(flag){
                u=v;
                continue;
            }
            int x=n;
            if(!(--gap[dep[u]]))return ans;//gap优化
            for(int i=pre[u];i!=-1;i=edge[i].next){
                if(edge[i].cap-edge[i].flow&&dep[edge[i].v]<x){
                    x=dep[edge[i].v];
                    cur[u]=i;//常数优化
                }
            }
            dep[u]=x+1;
            gap[dep[u]]++;
            if(u!=s)//当前点没有增广路则后退一个点
            u=edge[path[u]^1].v;
        }
        return ans;
    }
}F;

int cap[MAXN];
int id[MAXN][MAXN];
int low[MAXN][MAXN];

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int n,m,u,v,tmp;
    while(scanf("%d %d",&n,&m)==2){
        int s = 0,t = n+m+1,ss=t+1,tt = ss+1;
        F.init(tt);
        memset(cap,0,sizeof(cap));
        memset(id,0,sizeof(id));
        memset(low,0,sizeof(low));
        for(int i=1;i<=m;++i){
            scanf("%d",&tmp);
            F.AddEdge(i+n,t,INF-tmp);               //有下界
            cap[i+n]-=tmp, cap[t]+= tmp;
        }
        for(int i=1;i<=n;++i){
            int c,d;
            scanf("%d %d",&c,&d);
            F.AddEdge(s,i,d);                       //有上界
            for(int j=1;j<=c;++j){
                int L,R;
                scanf("%d %d %d",&u,&L,&R);
                u++;
                F.AddEdge(i,u+n,R-L);           //有上下界
                cap[i] -= L, cap[u+n] += L;
                low[i][u] = L;
                id[i][u] = F.tot-2;
            }
        }
        F.AddEdge(t,s,INF);
        int sum =0;
        for(int i=0;i<=t;++i){
            if(cap[i]>0){
                sum+= cap[i];
                F.AddEdge(ss,i,cap[i]);
            }
            else{
                F.AddEdge(i,tt,-cap[i]);
            }
        }

        int res = F.isap(ss,tt);
        if(res!=sum){
            printf("-1\n");
        }
        else{
            res = F.isap(s,t);
            printf("%d\n",res);
            for(int i=1;i<=n;++i){
                for(int j=1;j<=m;++j){
                    if(id[i][j]){
                        printf("%d\n",F.edge[id[i][j]].flow+low[i][j]);
                    }
                }
            }
        }
        printf("\n");
    }
    return 0;
}