配置魔药 [NOIP模拟] [DP] [费用流]

问题描述
在《Harry Potter and the Chamber of Secrets》中,Ron 的魔杖因为坐他老爸的 Flying Car 撞到了打人柳,不幸被打断了,从此之后,他的魔杖的魔力就大大减少,甚至没办法执行他施的魔咒,这为 Ron 带来了不少的烦恼。这天上魔药课,Snape 要他们每人配置一种魔药(不一定是一样的),Ron 因为魔杖的问题,不能完成这个任务,他请 Harry 在魔药课上(自然是躲过了 Snape 的检查)帮他配置。现在 Harry 面前有两个坩埚,有许多种药材要放进坩埚里,但坩埚的能力有限,无法同时配置所有的药材。一个坩埚相同时间内只能加工一种药材,但是不一定每一种药材都要加进坩埚里。加工每种药材都有必须在一个起始时间和结束时间内完成(起始时间所在的那一刻和结束时间所在的那一刻也算在完成时间内),每种药材都有一个加工后的药效。现在要求的就是 Harry 可以得到最大的药效。

输入
输入文件的第一行有 2 个整数,一节魔药课的 t(1≤t<≤500)和药材数 n(1≤n≤100)。
输入文件第 2 行到 n+1 行中每行有 3 个数字,分别为加工第 i 种药材的起始时间 t1、结束时间 t2、(1≤t1≤t2≤t)和药效 w(1≤w≤100)。

输出
输出文件 medic.out 只有一行,只输出一个正整数,即为最大药效。

输入样例
7 4
1 2 10
4 7 20
1 3 2
3 7 3

输出样例
35

注释
本题的样例是这样实现的:第一个坩埚放第 1、4 种药材,第二个坩埚放第
2、3 种药材。这样最大的药效就为 10+20+2+3=35。
如图,数字为时间轴。

数据规模

对于 30%的数据
1<=t<=500
1<=n<=15
1<=w<=100
1<=t1<=t2<=t

对于 100%的数据
1<=t<=500
1<=n<=100
1<=w<=100
1<=t1<=t2<=t

分析

这道题我和std写的不太一样，std用的是DP，而我太弱了，只会写一个费用流...

一、STD的DP

看完题目后，对题目分析可知，此题的最优解法就是动态规划。[???]

当然，因为有两个坩锅，所以明显是一道双进程动态规划题目。因此，先用动态规划求解一个坩锅能达到的最大药效，把已用的药材去掉，再次动态规划的方法是不可行的！

1．分析最优子结构：

数据备注：

t1[i]表示第i种药材的起始时间

t2[i]表示第i种药材的结束时间

w[i]表示第i种药材的药效

time表示总时间 n表示药材总数

（为了让大家更好理解 先讲一种未优化的算法）

设动态规划数组 dp[i][j][k] 表示前i种药材放入两个坩锅，第一个坩锅达到时间j，第二个坩锅达到k时所能达到的最大药效。题目的解就是dp[n][time][time];

因为要知道在time时刻两个坩锅的效益和，则需要用到它的子结构的最优值。

分析子结构的最优值的取得条件：

对于第i种药材，放入两个坩锅，有三种处理方法：

1． 把它放入第一个坩锅；

2． 把它放入第二个坩锅；

3． 不放入任何坩锅

对1：

　　dp[i][j][k]=dp[i-1][t1[i]-1][k]+w[i];   条件：仅当j=t2[i];

对2：

　　dp[i][j][k]=dp[i-1][j][t1[i]-1]+w[i];   条件：仅当k=t2[i];

对3：

　　dp[i][j][k]=max{ dp[i-1][j][k],       无条件　　

　　dp[i][j-1][k],       条件 j>0

　　dp[i][j][k-1],       条件 k>0

因此 子结构dp[i][j][k]的取值就是对1，2，3种状态的最大值

即：

dp[i][j][k]=max{

　　dp[i-1][t1[i]-1][k]+w[i];   条件：仅当j=t2[i];

　　dp[i-1][j][t1[i]-1]+w[i];   条件：仅当k=t2[i];

　　dp[i-1][j][k],             无条件

　　dp[i][j-1][k],             条件 j>0

　　dp[i][j][k-1],             条件 k>0

}

 

2．解决后效性：

为了解决后效性，在这里，当且仅当j=t1[i]或k=t1[i]时，药材才会被放入坩锅内，且保证了同一种药品不会在以后被多次放入或者是同时放入二个坩锅，当然，仅仅是这样还是不能保证能求出最优解，因为在计算过程中，结构会被刷新，因此对于结束时间较晚的药材，若在结束时间较前的药材先被计算，则较前的药材就以为价值小而不会被记录，因此就应该在动态规划之前将数据按结束时间t2[i]升序排序。因此，我们完美的消除了后效性。

 

3.优化问题：

     1．时间复杂度的优化：

     根据对称性，两个坩锅不计先后，且一摸一样，因此dp[i][j][k]等价于dp[i][k][j]，因此，在循环的时候可以令j<=k;然后加几个判断即可。具体方法不再赘述，请自行解决。

     2．空间复杂度的优化：

 在求解的过程中 即：dp[i][j][k]的值 只与 dp[i-1][…][…]的值有关，因此可以将数组降为2维 即：dp[j][k]，具体方法不再赘述。可以看标程，标程有两个，一个是优化过的，一个是未经过优化的。

因此，对于这道题目，

　　近似最优时间复杂度为O(n^3)

　　近似最优空间复杂度为O(n^2)

#include<stdio.h>
int dp[501][501]={0};
int t1[101]={0},t2[101]={0},w[101]={0},t,n;

void quick_sort(int l,int r)//按t2升序排序 
{int i,k,a;
 if(l>=r)
   return;
 k=l-1;
 for(i=l;i<r;i++)
   if(t2[i]<t2[r])
    {k++;
     a=t2[k];
     t2[k]=t2[i];
     t2[i]=a;
     a=t1[k];
     t1[k]=t1[i];
     t1[i]=a;
     a=w[k];
     w[k]=w[i];
     w[i]=a;
    }
     a=t2[k+1];
     t2[k+1]=t2[r];
     t2[r]=a;
     a=t1[k+1];
     t1[k+1]=t1[r];
     t1[r]=a;
     a=w[k+1];
     w[k+1]=w[r];
     w[r]=a;
 quick_sort(l,k);
 quick_sort(k+2,r);
}

FILE *fin,*fout;
main()
{fin=fopen("medic.in","r");
 fout=fopen("std.out","w");
 int i,j,k,q,a;
 fscanf(fin,"%d%d",&t,&n);
 for(i=1;i<=n;i++)
   fscanf(fin,"%d%d%d",&t1[i],&t2[i],&w[i]);
 quick_sort(1,n);
 for(i=1;i<=n;i++)//动态规划 
   for(j=t;j>=0;j--)
     for(k=t;k>=0;k--)
      {if(j>=t2[i])
         if(dp[j][k]<dp[t1[i]-1][k]+w[i])
           dp[j][k]=dp[t1[i]-1][k]+w[i];
       if(k>=t2[i])
         if(dp[j][k]<dp[j][t1[i]-1]+w[i])
           dp[j][k]=dp[j][t1[i]-1]+w[i];
      }
 fprintf(fout,"%d",dp[t][t]);
 fclose(fin);
 fclose(fout);
}

二、我写的费用流我看到这道题，嘴上笑嘻嘻，心里mmp，看起来又是一道DP/贪心题？

我最讨厌的就是这个东西了

于是联想以前的题目想到了USACO Nov07挤奶时间 那到题，是个单线程的求最大收益值，于是我就u->v连了条权值为收益的边，跑遍最长路

这道题不就是把单线程改成了双线程吗？两次最长路是显然错误的，因为不一定是最优。但他在跑完之后能反悔就好了

反悔？我们想到了网络流的反向边，于是我们尝试把这道题转化成一个网络流的模型

u->v+1连一条费用为收益，流量为1的边(v+1是因为包括了末节点的时间)，然后从起点到终点，连一条i->i+1，费用为0，流量为2的边

这样限制了进程数为2，同时跑一边最大费用最大流，就AC了 （然后这样的算法完爆STD？测试我的0s ，std 0.7s）

#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define RG register int
#define rep(i,a,b)    for(RG i=a;i<=b;i++)
#define per(i,a,b)    for(RG i=a;i>=b;i--)
#define ll long long
#define inf (1<<30)
#define maxm 5005
using namespace std;
int n,m,S,T,cnt=1;
int head[maxm],dis[maxm],step[maxm],vis[maxm];
struct E{
    int u,v,fl,cost,next;
}e[maxm];
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

inline void add(int u,int v,int fl,int cost)
{
    e[++cnt].u=u,e[cnt].v=v,e[cnt].fl=fl,e[cnt].cost=cost,e[cnt].next=head[u],head[u]=cnt;swap(u,v);
    e[++cnt].u=u,e[cnt].v=v,e[cnt].fl=0,e[cnt].cost=-cost,e[cnt].next=head[u],head[u]=cnt;
}

bool SPFA()
{
    memset(dis,63,sizeof(dis));
    memset(step,-1,sizeof(step));
    memset(vis,0,sizeof(vis));
    queue<int> que;que.push(S),dis[S]=0;RG u,v;
    while(!que.empty())
    {
        u=que.front(),que.pop();vis[u]=0;
        for(RG i=head[u];i;i=e[i].next)
        {
            v=e[i].v;
            if(e[i].fl&&dis[v]>dis[u]+e[i].cost)
            {
                dis[v]=dis[u]+e[i].cost;
                step[v]=i;
                if(!vis[v])    vis[v]=1,que.push(v);
            }
        }
    }
    return (step[T]!=-1);
}

void MCMF()
{
    int ans=0;
    while(SPFA())
    {
        int fl=inf;
        for(RG i=step[T];i!=-1;i=step[e[i].u])    fl=min(fl,e[i].fl);
        for(RG i=step[T];i!=-1;i=step[e[i].u])    e[i].fl-=fl,e[i^1].fl+=fl,cout<<e[i].v<<" ";
        ans+=dis[T];
    }
    cout<<-ans;
}

int main()
{
    freopen("medic.in","r",stdin);
    freopen("medic.out","w",stdout);
    n=read(),m=read();S=0,T=n+1;
    for(RG i=1,u,v,cost;i<=m;i++) u=read(),v=read(),cost=read(),add(u,v+1,1,-cost);
    rep(i,2,n)    add(i-1,i,2,0);
    add(S,1,2,0);add(n,T,2,0);
    MCMF();
    return 0;
}