NOIP2009 最优贸易
[NOIP2009 提高组] 最优贸易
是个人就会的solution：
//https://ac.nowcoder.com/acm/problem/16611
#include
#define LOCAL
using namespace std;
/*
大致思路就是： 先用非常愚蠢的办法求出任一点两点之间是否联通，
然后再遍历每一对联通点，看是否能够与始点和终点联通（有方向性），
如果能的话，求出差价，然后选择性更新结果
*/
const int INF=5e5+1;
const int maxn=1e3+10;
bool link[maxn][maxn]={0};
int w[maxn];
int main(){
#ifdef LOCAL
freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
for (int i=1;i<=n;++i) {
cin>>w[i];
link[i][i]=1;
}
for (int i=1;i<=m;++i){
int x,y,z;
cin>>x>>y>>z;
link[x][y]=1;
if (z==2) link[y][x]=1;
}
for (int k=1;k<=n;++k) for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) {
link[i][j]=link[i][j]||(link[i][k] && link[k][j]);
}
int ans=-INF;
for (int i=1;i<=n;++i){
for (int j=1;j<=n;++j){
if (link[i][j] && link[1][i] && link[j][n]){
int tmpw=w[j]-w[i];
if (tmpw>ans) ans=tmpw;
}
}
}
cout< 看了dalao的思路后写的。。。
/*
发自内心的感觉，这个题其中最重要的一个问题就是如果搜索，那么什么条件下stop
如果不stop就会产生死循环！
这个题第一感觉就是要找到一个最大值一个最小值，小的在前面（不过这两个极值必须在某种条件下，
防止二点之间无法到达，同时又漏掉了事实上更优的结果）
看了题解之后（真的很自责，无奈，看题是在不会，但不能总是看题解啊，，，），
发现dalao思路：
从第一个点去dfs,记录从第一个到当前个中出现的最小值，并更新，然后遍历与该点所连的点
在 当该点不是更小值且该点作为最大值所得差价不比之前走到该点时所的差价更优（可能之前没有走过，就是0）时终止
how to understand?
首先，当它是更小值时，当然不能停（如果可以继续的话），毕竟接下来就有可能找到更佳情况
首先，出现死循环的原因是某些路是双向的，为什么要拐回去呢？
因为后来找到了更小值，可以与前面的更大值形成差价，反正是可以再拐回来的
那我觉得 什么时候没必要返回，什么时候就该终止了
第一个条件还好理解，毕竟找到最小值肯定是要回去检测一番（注意mi[x]表示走到x点时最小的值，可能是之前走过的，也可能是没走过的，都要选择性更新）
特别是第二个条件，十分隐含！！！！！！！！：看括号里面的条件！：
如果到该点时的最大差价（通过dp之前那个点之前的最大差价和该点与当前最小值的差）比之前到达该点时的最大差价高
，说明后来发现了最小值后没有返回来检查下前面可以回溯的点，反之，说明这里已经被最新的最小值检测过了，就没必要继续检测下去了
perfect，解释通了
但为什么我不会呢？而且废了很长时间采用自己不严谨的话解释的让自己通了（不是，是懒得解释了吧）
首先，没有能够抓住一个思路深入进去（就是没想通怎么终止搜索，就没想下去了），
其实即使想不通，也可以举实例去想想有哪些需要考虑的地方；
没抓住本质：为啥要回去（怎么防止反复回去 ）
*/
//https://www.luogu.com.cn/problem/P1073
//https://ac.nowcoder.com/acm/problem/16611
#include
#include
#define LOCAL
using namespace std;
const int INF=5e5+1;
const int maxn=1e5+10;
int w[maxn];
vector link[maxn];
int mi[maxn]={0};
int f[maxn];
void dfs(int x,int md,int pre){ // x : current point md: current minimum difference pre: the previous point
int flag=1;
int minx=min(md,w[x]);
if (minxf[x])f[x]=maxd,flag=0;
if (flag) return ;
for (int i=0;i<(int) link[x].size();++i) dfs(link[x][i],minx,x);
}
int main(){
#ifdef LOCAL
freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
for (int i=1;i<=n;++i) {
cin>>w[i];
f[i]=-INF;
}
for (int i=1;i<=m;++i){
int x,y,z;
cin>>x>>y>>z;
link[x].push_back(y);
if (z==2) link[y].push_back(x);
}
dfs(1,w[1],0);
cout<