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
2
5 6
3 9
1 2
样例输出 Sample Output
5
原图缩点，得到一条链
那么只需要探索链的起点即可
可以想到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 1001using 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[];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=;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=;i<=n;i++)
if(!dfn[i]) tarjan(i);
for(int i=;i<=tot;i++)
if(col[from[i]]!=col[to[i]]) in[col[to[i]]]++;
int m=;
for(int i=;i<=cnt;i++)
if(!in[i]) m+=na[i];
for(int i=;i<=cnt;i++)
if(!in[i])
for(int j=m;j>=;j--)
if(j-na[i]>=) dp[j]=min(dp[j-na[i]],dp[j]+nb[i]);
else dp[j]+=nb[i];
int ans=m;
for(int i=m;i>=;i--) ans=min(ans,max(i,dp[i]));
printf("%d",ans);
}int main()
{
init();
solve();
}
