ZOJ 3229 Shoot the Bullet | 有源汇可行流

题目:

射命丸文要给幻想乡的居民照相，共照n天m个人，每天射命丸文照相数不多于d个，且一个人n天一共被拍的照片不能少于g个，且每天可照的人有限制，且这些人今天照的相片必须在[l,r]以内，求是否有可行解，如果有则输出最多照片数，并且输出每天每个可以被照的人的被照的照片数。

---

题解:

建个源点向每天连容量为[0,d],每天向每个人连[l,r],每个人向汇点连[g,INF]

我们已经建好了一个有源汇的有上下界网络

我们再从T向S连[0,INF]就变了一个无源汇!

这个时候我们套用无源汇模板即可

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#define N 1505

#define M 750005

#define INF 0x3f3f3f3f

using namespace std;

int read()

{

    int ret=,neg=;char j=getchar();

    for (;j>'' || j<'';j=getchar())

    if (j=='-') neg=-;

    for (;j>='' && j<='';j=getchar())

    ret=ret*+j-'';

    return ret*neg;

}

struct adj {int nxt,v,w;}e[M];

int head[N],du[N],id[][],low[][],lev[N],cur[N],dis[N];

int sum,ans,ecnt=,S,T,n,m,St,Ed;

queue <int> q;

void add(int u,int v,int w)

{

    e[++ecnt].v=v;e[ecnt].w=w;e[ecnt].nxt=head[u];head[u]=ecnt;

    e[++ecnt].v=u;e[ecnt].w=;e[ecnt].nxt=head[v];head[v]=ecnt;

}

void init()

{

    sum=ans=;ecnt=;

    memset(head,,sizeof(head));

    memset(du,,sizeof(du));

    memset(id,,sizeof(id));

}

bool Bfs()

{

    while (!q.empty()) q.pop();

    for (int i=;i<=T;i++)

    cur[i]=head[i],dis[i]=-;

    dis[S]=;q.push(S);

    while (!q.empty())

    {

    int u=q.front();q.pop();

    for (int i=head[u],v;i;i=e[i].nxt)

        if (e[i].w && dis[v=e[i].v]==-)

        {

        dis[v]=dis[u]+,q.push(v);

        if (v==T) return ;

        }

    }

    return ;

}

int Dfs(int u,int flow)

{

    if (u==T) return flow;

    int ret=,delta;

    for (int &i=cur[u],v;i;i=e[i].nxt)

    if (e[i].w && dis[v=e[i].v]==dis[u]+)

    {

        delta=Dfs(v,min(e[i].w,flow-ret));

        if (delta)

        {

        e[i].w-=delta;

        e[i^].w+=delta;

        ret+=delta;

        if (ret==flow) break;

        }

    }

    return ret;

}

int main()

{

    while (scanf("%d%d",&n,&m)!=EOF && n)

    {

    St=m+n+,Ed=m+n+;

    init();

    for (int i=,w;i<=m;i++)

        add(i,Ed,INF-(w=read())),du[i]-=w,du[Ed]+=w;

    for (int i=m+,c,d;i<=m+n;i++)

    {

        c=read();d=read();

        add(St,i,d);

        for (int j=;j<=c;j++)

        {

        int t=read()+,l=read(),r=read();

        add(i,t,r-l);du[i]-=l;du[t]+=l;

        id[i-m][t]=ecnt;low[i-m][t]=l;

        }

    }

    int h1=head[St],h2=head[Ed];

    add(Ed,St,INF);

    S=Ed+;T=S+;

    for (int i=;i<=m+n+;i++)

        if (du[i]>) add(S,i,du[i]),sum+=du[i];

        else if (du[i]<) add(i,T,-du[i]);

    while (Bfs()) ans+=Dfs(S,INF);

    if (ans!=sum) puts("-1");

    else

    {

        head[S]=head[T]=-;

        head[St]=h1;head[Ed]=h2;

        S=St;T=Ed;

        while (Bfs()) ans+=Dfs(S,INF);

        printf("%d\n",ans);

        for (int i=;i<=n;i++)

        for (int j=;j<=m;j++)

            if (id[i][j])

            printf("%d\n",e[id[i][j]].w+low[i][j]);

    }

    putchar('\n');

    }

    return ;

}