USACO22OPEN-Bronze A

前言（Front talk)

$\qquad$USACO好像很喜欢靠二分答案呢~

网址（Website）

洛谷： USACO22OPEN Alchemy B

SPOJ：题目详情 - Alchemy - Super

SPOJ：题解 - Alchemy - Super

题目（Problem）

$\qquad$总是热衷于培养新的爱好的奶牛 $Bessie$ 正在学习如何转化金属。对于 $1 \le i \le N \le 100$，她有 $a_i\ (0 \le a_i \le 10^4)$单位的金属 $i$。此外，她知道 $K$（$1\le K< N$）个配方，她可以融合若干种金属各一单位，制造一单位编号大于所有被融合金属的金属。另外保证，对于每种金属，$Bessie$ 最多知道一种制造该金属的配方。

$\qquad$计算经过一系列转化后，$Bessie$ 可能拥有的金属 $N$ 的最大单位数。

输入格式（Input）

$\qquad$输入的第一行包含 $N$。

$\qquad$第二行包含 $N$ 个整数 $a_i$。

$\qquad$第三行包含 $K$。

$\qquad$以下 $K$ 行每行包含两个整数 $L$ 和 $M$（$M\ge 1$），随后是 $M$ 个整数。后 $M$ 个整数表示配方中用于制造一单位金属 $L$ 所需要被融合的金属。输入保证 $L$ 大于这 $M$ 个数。

输出格式（Output）

$\qquad$输出在应用一系列零次或多次转化后，$Bessie$ 可能拥有的金属 $N$ 的最大单位数。

样例（Example）

样例输入

样例输出

提示（Notice）

样例解释

在这个例子中，以下是一种最优的转化方式：

将一单位金属 $1$ 转化为金属 $2$。
将一单位金属 $2$ 转化为金属 $3$。
将一单位金属 $3$ 和金属 $4$ 转化为金属 $5$。

现在 $Bessie$ 还有一单位金属 $1$ 和一单位金属 $5$。她无法再制造更多的金属 $5$。

测试点性质

测试点 $2$ 中，对于 $1\le i< N$，一单位金属 $i$ 可以被转化为一单位金属 $i+1$；
测试点 $3-4$ 中，每个配方均将一单位的一种金属转化为另一种金属；
测试点 $5-11$ 没有额外限制。

题解（Solution）

$\qquad$数据范围需要注意以下，需要 $unsigned\ long\ long$ 。

$\qquad$如果正向合成的话，需要考虑当前的金属需要合成成哪些其他金属，而我们又不知道合成了新的金属后会不会根本无法合成第 $n$ 号金属，如果想知道这件事，我们就需要先遍历一遍，再来判断当前点，那还不如直接倒着来。

$\qquad$~~一秒就想到了二分答案~~，因为答案有个性质：有解的单调性（就是任何小于答案的值都有解，而任何大于答案的值都无解），因此想到二分答案。

$\qquad$ 时间复杂度：$O\left((n+m) \log \sum\limits_{i=1}^{n} a_{i}\right)$

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;++i)
#define Rof(i,l,r) for(int i=l;i>=r;--i)
using namespace std;
#define P pair<int,int>
#define int unsigned long long
#define Fi first
#define Se second
inline int input(){int x;return cin>>x,x;}
const int inf = 1e6+14;
const int N = 10123;
vector<int>ft[N];
int n,k,a[N],lmt[N];
priority_queue<P> q;
inline bool check(int st,int mid){
	For(i,1,n) lmt[i]=0;lmt[n]=mid;
	
	Rof(i,n,1){
		if(lmt[i]>a[i] && ft[i].empty()) return false;
		if(lmt[i]<=a[i]) continue;
		lmt[i]-=a[i];
		for(auto y:ft[i]) lmt[y]+=lmt[i];
	}return true;
	
    //广搜的方法卡常
//	while(q.size()) q.pop();
//	q.push({st,mid});
//	while(q.size()){
//		int x=q.top().Fi,hav=q.top().Se;q.pop();
//		if(hav>lmt[x]) hav-=lmt[x],lmt[x]=0;
//		else {lmt[x]-=hav;continue;}
//		if(ft[x].empty() && hav) return false;
//		for(auto y:ft[x]) q.push({y,hav});
//	}return true;
}

//inline bool check(int mid){
//	
//}

inline int Two_division(){
	int l=0,r=inf,mid,res;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(n,mid)) l=mid+1,res=mid;
		else r=mid-1;
	}return res;
}

inline bool cmp(P a,P b){return a.Fi>b.Fi;}
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	string str("alchemy");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	cin>>n;For(i,1,n) a[i]=input();
	cin>>k;For(i,1,k){
		int x=input(),m=input();
		For(j,1,m){int y=input();ft[x].push_back(y);}
	}cout<<Two_division()<<'\n';
	return 0;	
}