NOI2008志愿者招募

Posted on By 二价氢

这一题有点麻烦

后来参看了BYVoid大神犇的题解才有点明白

一直以为这是DP233333

好了,下面就是我的题解:

例如,有这样的一组数据

5 6
5 7 4 3 2
1 4 3
3 5 2
2 4 5
1 3 2
1 1 1
2 3 3

那么,我们有:

我居然突然明白了为何是网络流了,这题居然是线性规划!!!

好了,我们现在就要求的最小值!

这里是个6元的不等式,要用六维的生物做,题目里有10000维,那么要10000维生物做,那里的图差不多就是这样(笑~)

好了,我们可以这样:

再加上一个式子

用第个式子减去第个式子,有:

接下来是构图,有以下约定:

设一个通式,即第个式子表示为:

则连边:,反之连边:,边权为0,容量为

式中,的系数为正,式中,的系数为负,则连边边权为,容量为INF

式中,的系数为正,式中,的系数为负,则连边边权为0,容量为INF

然后,求的最小费用最大流即可

下面是AC-Code:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN=1005,MAXM=40005;
const long long INF=0x7fffffff;
//网络流用
struct Edge{int next,op,t,v,w;}E[MAXM];
int Pfirst[MAXN];
int DIS[MAXN];
int Pre[MAXN];
int Edg[MAXN];
int NEED[MAXN];
bool INQ[MAXN];
int M,N;
int COST;
int S=0,T;
int totE=0;
void addedge(int s,int t,int w,int v)//源汇权容
{
    int E1=++totE,E2=++totE;
    E[E1].t=t;E[E2].t=s;
    E[E1].next=Pfirst[s];E[E2].next=Pfirst[t];
    E[E1].op=E2;E[E2].op=E1;
    E[E1].w=w;E[E2].w=-w;
    E[E1].v=v;E[E2].v=0;
    Pfirst[s]=E1;Pfirst[t]=E2;
}
void Read()
{
    int SS,TT,CC,c;
    scanf("%d%d",&N,&M);
    T=N+2;
    for (int i=1;i<=N;i++)
        scanf("%d",&NEED[i]);
    for (int i=1;i<=N+1;i++)
    {
        if (i!=1)
            addedge(i,i-1,0,INF);
        c=NEED[i]-NEED[i-1];
        if (c>=0)
            addedge(0,i,0,c);
        else
            addedge(i,T,0,-c);
    }
    for (int i=1;i<=M;i++)
    {
        scanf("%d%d%d",&SS,&TT,&CC);
        addedge(SS,TT+1,CC,INF);
    }
}
void SPFA()
{
    int u,v;
    memset(DIS,0x3f,sizeof(DIS));
    memset(Pre,-1,sizeof(Pre));
    memset(INQ,0,sizeof(INQ));
    DIS[S]=0;
    queue <int>Q;
    Q.push(S);
    while (!Q.empty())
    {
        u=Q.front();
        Q.pop();
        INQ[u]=false;
        for (int pv=Pfirst[u];pv;pv=E[pv].next)
        {
            v=E[pv].t;
            if (E[pv].v>0)
            {
                if (DIS[v]>(DIS[u]+E[pv].w))
                {
                    if (!INQ[v])
                    {
                        Q.push(v);
                        INQ[v]=true;
                    }
                    Edg[v]=pv;
                    Pre[v]=u;
                    DIS[v]=DIS[u]+E[pv].w;
                }
            }
        }
    }
}
void MaxFlow()
{
    int u,v;
    int tmaxflow;
    while (1)
    {
        SPFA();
        if (Pre[T]==-1)
            break;
        tmaxflow=INF;
        for (v=T;Pre[v]!=-1;v=Pre[v])
        {
            tmaxflow=min(tmaxflow,E[Edg[v]].v);
        }
        for (v=T;Pre[v]!=-1;v=Pre[v])
        {
            COST+=tmaxflow*E[Edg[v]].w;
            E[Edg[v]].v-=tmaxflow;
            E[E[Edg[v]].op].v+=tmaxflow;
        }
    }
    printf("%d\n",COST);
}
int main()
{
    Read();
    MaxFlow();
    return 0;
}