【bzoj1061】【未完】[Noi2008]志愿者招募

2015.04.15 07:23 Wed | 3次阅读 | 旧日oi | 固定链接 | 源码

Description

申奥成功后,布布经过不懈努力,终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题:为即将启动的奥运新项目招募一批短期志愿者。经过估算,这个项目需要N 天才能完成,其中第i 天至少需要Ai 个人。 布布通过了解得知,一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天,招募费用是每人Ci 元。新官上任三把火,为了出色地完成自己的工作,布布希望用尽量少的费用招募足够的志愿者,但这并不是他的特长!于是布布找到了你,希望你帮他设计一种最优的招募方案。

Input

第一行包含两个整数N, M,表示完成项目的天数和可以招募的志愿者的种类。 接下来的一行中包含N 个非负整数,表示每天至少需要的志愿者人数。 接下来的M 行中每行包含三个整数Si, Ti, Ci,含义如上文所述。为了方便起见,我们可以认为每类志愿者的数量都是无限多的。

Output

仅包含一个整数,表示你所设计的最优方案的总费用。

Sample Input

3 3
2 3 4
1 2 2
2 3 5
3 3 2

Sample Output

14

HINT

招募第一类志愿者3名,第三类志愿者4名 30%的数据中,1 ≤ N, M ≤ 10,1 ≤ Ai ≤ 10; 100%的数据中,1 ≤ N ≤ 1000,1 ≤ M ≤ 10000,题目中其他所涉及的数据均 不超过2^31-1。

题解

线性规划网络流……shenmegui……
这种用不等式建图的题还真是第一次见,看了建图方法之后感觉好像的确比较科学但是具体不知道怎么证……再留个坑吧
设每种志愿者招募x[i]人,对于每一天,列出一个不等式,左边减去一个y[i],把不等号变成等号。然后添加第0个和第n+1个不等式,左右都为0,之后用第一个减第0个,第2个减第1个……第n+1个减第n个,得到n+1组不等式。
观察不等式,我们可以发现,每一项恰好出现过一正一负两次,很像网络流中的流量平衡,而常数项,可以看做是源点或汇点的流量,我也不知道这是为什么……
对于每个不等式,如果常数项c为正,和源点连一条权值为c,费用为0的边,否则和汇点连权值为-c,费用为0的边
若第i个不等式中x[i]为正,第j个中为负,则从i到j连一条容量inf,费用为c[i],可以发现就是从s[i]到t[i]+1
对于y[i]也是同理,连的边的费用是0,观察可以发现就是从i连到i+1.
然后跑最小费用最大流就行了。

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 100010
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,S,T;
int s,t,c,a[1005];
struct edge{
    int to;
    int next;
    int flow;
    int cost;
}e[200005];
int h[10005],tp;
void ae(int u,int v,int w,int c)
{
    e[tp].to=v;
    e[tp].next=h[u];
    e[tp].flow=w;
    e[tp].cost=c;
    h[u]=tp++;
}
void add(int u,int v,int w,int c)
{
    ae(u,v,w,c);
    ae(v,u,0,-c);
}
int dis[10005];
bool vis[10005];
queue<int> q;
int fa[10005],fr[10005];
bool spfa()
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[S]=0;
    while(!q.empty()) q.pop();
    q.push(S);
    while(!q.empty())
    {
        int u=q.front();q.pop();vis[u]=0;
        for(int v,i=h[u];i!=-1;i=e[i].next)
        if(e[i].flow&&dis[v=e[i].to]>dis[u]+e[i].cost)
        {
            dis[v]=dis[u]+e[i].cost;
            fa[v]=u;fr[v]=i;
            q.push(v);vis[v]=1;
        }
    }
    return dis[T]==inf;
}       
int dinic()
{
    int ans=0;
    while(!spfa())
    {
        int minn=inf,i;
        for(i=T;i;i=fa[i])
        minn=min(minn,e[fr[i]].flow);
        for(i=T;i;i=fa[i])
        {
            e[fr[i]].flow-=minn;
            e[fr[i]^1].flow+=minn;
            ans+=minn*e[fr[i]].cost;
        }
    }
    return ans;
}   
int main()
{
    //freopen("employee.in","r",stdin);
    memset(h,-1,sizeof(h));
    n=read();
    m=read();
    S=0;T=n+2;
    for(int i=1;i<=n;i++) 
    {
        a[i]=read();
        if(a[i]>a[i-1]) 
            add(S,i,a[i]-a[i-1],0);
        else
            add(i,T,a[i-1]-a[i],0);
    }
    add(n+1,T,a[n],0);
    for(int i=1;i<=m;i++)
    {
        s=read();t=read();c=read();
        add(s,t+1,inf,c);
    }
    for(int i=1;i<=n;i++)
    add(i+1,i,inf,0);
    printf("%d\n",dinic());
    return 0;
}```