codevs 1492 探案第二部

1492 探案第二部

时间限制: 1 s

空间限制: 128000 KB

题目描述 Description

我们伟大的 Sherlock·Holmes 先生最近遇上了一件相当棘手的案子，随着对案情逐渐深入的研究，他开始意识到：此案地域横跨欧洲，而起因可以追溯到50年前！为了尽快搜集各方面的线索，他决定与Dr. Watson分头行动。

Holmes列出了若干需要的线索：某处的一些雪茄烟灰；地下室油画上的颜料的呈色；Black兄弟与他们邻里的联系……诸如此类。而搜集这些线索需要一定的时间。不过，有些线索是相关联的，即在得到某个线索的时候，一并可以得出其他结论（我们可以认为这是不需要时间的）

请充分相信Holmes先生！他无比敏锐的思维足够将所有线索串联，以完美的推理侦破这件名噪一时的大案！

输入描述 Input Description

第一行为N，表示N个需要搜集的线索(N<=1000)

接下来N行，每行两个整数ai,bi, 分别表示Holmes，Watson搜集第i个线索所需要的时间。（ai,bi<=15）

接下来若干行，每行两个整数x,y，表示得到x, 同时能够得到y。

输出描述 Output Description

一个整数，即搜集所有线索的最小耗时。

样例输入 Sample Input

5 6

3 9

1 2

样例输出 Sample Output

原图缩点，得到一条链

那么只需要探索链的起点即可

可以想到dp[i][j] 表示第1个人用时为i，第2个人用时为j时否可行

把第二维压去

dp[i] 表示第1个人用时为i时，第2个人的最小用时

枚举第i个任务，枚举当前第1个人用时为j

如果第1个人在j用时能做这个任务那么

dp[j]=min（dp[j-timea[i]]，dp[j]+timeb[i]）即给第一个人做、第二个人做取最优

如果第1个人在j用时不能做这个任务，那么只能给第2个人做

dp[j]+=timeb[i]

最后答案就是枚举所有的i，ans=min（max（i，dp[i]））

#include<cstdio>
#include<algorithm>

#define N 1001

using namespace std;

int n,a[N],b[N];

int front[N],nxt[N*N],to[N*N],tot,from[N*N];

int col[N],cnt;
int st[N],top;
int dfn[N],low[N],tim;
bool ins[N];

int in[N];
int na[N],nb[N];

int dp[15001];

void add(int u,int v)
{
    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; from[tot]=u;
}

void init()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
    int x,y;
    while(scanf("%d%d",&x,&y)!=EOF) add(x,y);
}

void tarjan(int u)
{
    dfn[u]=low[u]=++tim;
    ins[u]=true;  st[++top]=u;
    for(int i=front[u];i;i=nxt[i])
        if(!dfn[to[i]]) tarjan(to[i]),low[u]=min(low[u],low[to[i]]);
        else if(ins[to[i]]) low[u]=min(low[u],dfn[to[i]]); 
    if(low[u]==dfn[u])
    {
        col[u]=++cnt; ins[u]=false;
        na[cnt]=a[u]; nb[cnt]=b[u];
        while(st[top]!=u) 
        {
            na[cnt]=min(na[cnt],a[st[top]]);
            nb[cnt]=min(nb[cnt],b[st[top]]);
            col[st[top]]=cnt;ins[st[top--]]=false;
        }
        top--;
    }
}

void solve()
{
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    for(int i=1;i<=tot;i++)
        if(col[from[i]]!=col[to[i]]) in[col[to[i]]]++;
    int m=0;
    for(int i=1;i<=cnt;i++)
        if(!in[i]) m+=na[i];
    for(int i=1;i<=cnt;i++)
        if(!in[i])
            for(int j=m;j>=0;j--)
                if(j-na[i]>=0) dp[j]=min(dp[j-na[i]],dp[j]+nb[i]);
                else dp[j]+=nb[i];
    int ans=m;
    for(int i=m;i>=0;i--) ans=min(ans,max(i,dp[i]));
    printf("%d",ans);
}

int main()
{
    init();
    solve();
}