BZOJ3280/HNOI2013集训小R的烦恼

Posted on Jan 17, 2014 By 二价氢

参考：BZOJ1221

我们可以像下面这样建图

这里是原图的矢量图

下面是对图的解释

  1. 把每天拆成两个点\(x_i\)(图中蓝色正方形)和\(Y_i\)（图中红色圆形）分别表示第i天要用的学生和用过的学生。
  2. 源点\(S\)到所有\(x_i\)连一条容量为该天需用学生数，费用为f的边，表示新买学生。（橙色边）
  3. 所有\(x_i\)到汇点\(T\)连一条容量为该天需用学生数，费用为0的边，表示每天都必须用足够的学生。（紫色边）
  4. 然后每天会产生若干用过的学生，所以再从\(S\)向所有的\(y_i\) 连边，容量同样是该天需用学生数，费用为0。（青色边）
  5. 这样，对某天用完后的学生进行治疗就对应了\(y\)到\(x\)的边：
  6. A医院 ：从每个\(Y_i\)到\(x_{i+d_a+1}\)连边，容量为无穷，费用为\(p_a\)（蓝色边）
  7. B医院 ：从每个\(Y_i\)到\(x_{i+d_b+1}\)连边，容量为无穷，费用为\(p_b\)（绿色边）
  8. x医院 ：从每个\(Y_i\)到\(x_{i+d_x+1}\)连边，容量为无穷，费用为\(p_x\)（绿色边）
  9. 然后每天用过的学生可以拖延到下一天再送去治疗，所以每个\(y_i\)向\(Y_{i+1}\)连边，容量为无穷，费用为0。（红色边）

与BZOJ1221不同的是，这一题除了要求最小费用之外，还需要求最大流量

当最大流量<每天需要使用的学生数之和时，输出impossible

AC-Code：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
//--网络流
const int MAXN=2005,MAXM=50005,INF=99999999;
const int S=2000,S0=2001,T=2002;
struct Edge{int t,c,v,op,next;}E[MAXM];
int Dis[MAXN],Pre[MAXN],Edg[MAXN],pFirst[MAXN],totE;
bool Vis[MAXN];
int N,M,K;
int Cost,Flow;
void addedge(int s,int t,int c,int v)
{
    int E1,E2;
    E1=++totE;E2=++totE;
    E[E1].t=t;E[E1].v=v;E[E1].c=c;E[E1].op=E2;
    E[E1].next=pFirst[s];pFirst[s]=E1;
    E[E2].t=s;E[E2].v=0;E[E2].c=-c;E[E2].op=E1;
    E[E2].next=pFirst[t];pFirst[t]=E2;
}
inline int X(int i)
{
    return i*2-1;
}
inline int Y(int i)
{
    return i*2;
}
bool Spfa()
{
    memset(Dis,0x3f,sizeof(Dis));
    memset(Pre,-1,sizeof(Pre));
    memset(Edg,-1,sizeof(Edg));
    memset(Vis,0,sizeof(Vis));
    queue<int>Q;
    int u,v,t;
    Q.push(S);
    Dis[S]=0;
    while (!Q.empty())
    {
        u=Q.front();Q.pop();
        Vis[u]=false;
        for (t=pFirst[u];t;t=E[t].next)
        {
            v=E[t].t;
            if (E[t].v>0)
            {
                if (Dis[v]>Dis[u]+E[t].c)
                {
                    Dis[v]=Dis[u]+E[t].c;
                    Pre[v]=u;Edg[v]=t;
                    if (!Vis[v])
                    {
                        Q.push(v);
                        Vis[v]=true;
                    }
                }
            }
        }
    }
    return (Pre[T]!=-1);
}
void Work()
{
    int tmaxflow,u;
    while (Spfa())
    {
        tmaxflow=INF;
        for (u=T;Pre[u]!=-1;u=Pre[u])
            tmaxflow=min(tmaxflow,E[Edg[u]].v);
		Cost+=tmaxflow*Dis[T];
        Flow+=tmaxflow;
        for (u=T;Pre[u]!=-1;u=Pre[u])
        {
            E[Edg[u]].v-=tmaxflow;
            E[E[Edg[u]].op].v+=tmaxflow;
        }
    }
}
void solve(int casei)
{
    int TOTFLOW=0;
    int tmp,li,pi,di,qi;
    scanf("%d%d%d",&N,&M,&K);
    for (int i=1;i<=N;i++)
    {
        scanf("%d",&tmp);
        TOTFLOW+=tmp;
        addedge(S0  ,X(i),0,tmp);
        addedge(S   ,Y(i),0,tmp);
        addedge(X(i),T   ,0,tmp);
        if (i<N)
            addedge(Y(i),Y(i+1),0,INF);
    }
    for (int i=1;i<=M;i++)
    {
        scanf("%d%d",&li,&pi);
        addedge(S,S0,pi,li);
    }
    for (int i=1;i<=K;i++)
    {
        scanf("%d%d",&di,&qi);
        for (int j=1;j+di+1<=N;j++)
            addedge(Y(j),X(j+di+1),qi,INF);
    }
    Work();
	if (TOTFLOW==Flow)
		printf("Case %d: %d\n",casei,Cost);
	else
		printf("Case %d: impossible\n",casei);
}
void reset()
{
	memset(E,0,sizeof(E));
	memset(pFirst,-1,sizeof(pFirst));
	totE=Cost=Flow=0;
}
//--题目
int main()
{
	int T;
	scanf("%d",&T);
	for (int i=1;i<=T;i++)
	{
		reset();
		solve(i);
	}
    return 0;
}