【Luogu】P2488工作安排（费用流）

　　题目链接

　　这题……费用流即可……（哇啊要被打死辣）

　　然而我printf("%d")爆零四次

　　好的心如死灰

#include<cstdio>

#include<cstring>

#include<cctype>

#include<cstdlib>

#include<algorithm>

#include<queue>

#define maxn 1000010

using namespace std;

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

struct Edge{

    long long next,from,to,val,dis;

}edge[maxn*];

long long head[maxn],num;

inline void addedge(long long from,long long to,long long val,long long dis){

    edge[++num]=(Edge){head[from],from,to,val,dis};

    head[from]=num;

}

inline void add(long long from,long long to,long long val,long long dis){

    addedge(from,to,val,dis);

    addedge(to,from,,-dis);

}

inline long long count(long long i){    return i&?i+:i-;    }

long long Start,End;

long long dis[maxn];

bool vis[maxn];

long long pre[maxn];

long long flow[maxn];

long long spfa(){

    memset(dis,/,sizeof(dis));    dis[Start]=;    flow[Start]=dis[];

    memset(pre,,sizeof(pre));

    queue<long long>q;    q.push(Start);

    while(!q.empty()){

        long long from=q.front();q.pop();    vis[from]=;

        if(flow[from]==)    continue;

        for(long long i=head[from];i;i=edge[i].next){

            long long to=edge[i].to;

            if(dis[to]<=dis[from]+edge[i].dis||edge[i].val<=)    continue;

            dis[to]=dis[from]+edge[i].dis;

            pre[to]=i;    flow[to]=min(flow[from],edge[i].val);

            if(vis[to])    continue;

            vis[to]=;    q.push(to);

        }

    }

    if(pre[End]==)    return ;

    long long now=End;

    while(now!=Start){

        long long ret=pre[now];

        edge[ret].val-=flow[End];    edge[count(ret)].val+=flow[End];

        now=edge[ret].from;

    }

    return dis[End]*flow[End];

}

long long s[maxn];

int main(){

    long long m=read(),n=read();End=n+m+;

    for(long long i=;i<=n;++i){

        long long x=read();

        add(i+m,End,x,);

    }

    for(long long i=;i<=m;++i)

        for(long long j=;j<=n;++j){

            long long x=read();

            if(x)    add(i,j+m,0x7fffffff,);

        }

    for(long long i=;i<=m;++i){

        long long sum=read();

        for(long long j=;j<=sum;++j)    s[j]=read();

        for(long long j=;j<=sum;++j){

            long long x=read();

            add(Start,i,s[j]-s[j-],x);

        }

        long long x=read();

        add(Start,i,0x7fffffff,x);

    }

    long long ans=;

    while(){

        long long now=spfa();

        if(now==)    break;

        ans+=now;

    }

    printf("%lld",ans);

    return ;

}