怎么做网站后期推广,平面设计接单软件,哪个网站是营销型网站,产品设计和工业设计有什么区别农民约翰有N头奶牛(1N10,000)#xff0c;编号为1...N。每一头奶牛需要T(i)单位的时间来挤奶。不幸的是#xff0c;由于FJ的仓库布局#xff0c;一些奶牛要在别的牛之前挤奶。比如说#xff0c;如果奶牛A必须在奶牛B前挤奶#xff0c;FJ就需要在给奶牛B挤奶前结束给…农民约翰有N头奶牛(1N10,000)编号为1...N。每一头奶牛需要T(i)单位的时间来挤奶。不幸的是由于FJ的仓库布局一些奶牛要在别的牛之前挤奶。比如说如果奶牛A必须在奶牛B前挤奶FJ就需要在给奶牛B挤奶前结束给奶牛A的挤奶。 为了尽量完成挤奶任务FJ聘请了一大批雇工协助任务——同一时刻足够去给任意数量的奶牛挤奶。然而尽管奶牛可以同时挤奶但仍需要满足以上的挤奶先后顺序。请帮助FJ计算挤奶过程中的最小总时间。
输入格式 第 1 行两个空格分隔的整数N奶牛数量和 M挤奶约束数量;1 M 50,000。 第 2..1N 行第 i1 行包含 T(i) 的值 1 T(i) 100,000。 第 2N 到1NM 行每行包含两个空格分隔的整数 A 和 B表示奶牛 A 必须完全挤奶然后才能开始给奶牛 B 挤奶。这些限制永远不会形成循环因此解决方案总是可能的。
输出格式 挤奶所有奶牛所需的最短时间。
输入样例 3 1 10 5 6 3 2 输出样例 11 解析
提到先后顺序就不难想到拓扑排序。值得注意的是虽然这道题问的是总时间的最小值但我们要求的是这张图的最长路。下面我们来证明一下 首先要明确的是题目给定的图不一定连通样例就具有这个性质,因此我们就要把它分成多个部分。 接着可以得出两个结论每个部分之间是相互独立的用题目的话说就是可以同时挤奶每个部分内部是相互约束的必须要等前面的奶牛挤完后再挤下一只。 最后我们设每个部分的用时为 t1 ,t2 ,...,tk 不难得出总用时为 max{t1 ,t2 ,...,tk}即为原图最长路。
#include bits/stdc.h
using namespace std;
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
typedef pairint,int PII;
const int N2e610;
vector int g[N];
int d[N],t[N],w[N];
int n,m;
queue int q;
signed main()
{ios;cinnm;for (int i1;in;i) cint[i];while (m--){int a,b;cinab;g[a].push_back(b);d[b];}for (int i1;in;i){if (!d[i]) {q.push(i);w[i]t[i];}}while(q.size()){int uq.front();q.pop();for (auto x:g[u]){w[x]max(w[x],w[u]t[x]);d[x]--;if (!d[x]) q.push(x);}}int ans0;for (int i1;in;i) ansmax(ans,w[i]);coutans;return 0;
}
