USACO22OPEN-Bronze A

前言（Front talk)

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

网址（Website）

洛谷： USACO22OPEN Alchemy B

SPOJ：题目详情 - Alchemy - Super

SPOJ：题解 - Alchemy - Super

题目（Problem）

总是热衷于培养新的爱好的奶牛正在学习如何转化金属。对于，她有单位的金属。此外，她知道（）个配方，她可以融合若干种金属各一单位，制造一单位编号大于所有被融合金属的金属。另外保证，对于每种金属，最多知道一种制造该金属的配方。

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

输入格式（Input）

输入的第一行包含。

第二行包含个整数。

第三行包含。

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

输出格式（Output）

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

样例（Example）

样例输入

样例输出

提示（Notice）

样例解释

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

将一单位金属转化为金属。
将一单位金属转化为金属。
将一单位金属和金属转化为金属。

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

测试点性质

测试点中，对于，一单位金属可以被转化为一单位金属；
测试点中，每个配方均将一单位的一种金属转化为另一种金属；
测试点没有额外限制。

题解（Solution）

数据范围需要注意以下，需要。

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

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

时间复杂度：

代码（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;	
}