在1個魔法森林中，有n個節點(n<=50000)，m條邊(m<=100000)，每一個節點有兩個值ai,bi，1<=ai,bi<=50000。有1個精靈要從節點1到達節點n，1個節點i可以經過的要求是它攜帶的兩個值A，B可滿足A>=ai，B>=bi，求min(A+B)。
本題目的標準解法是LCT(link-cut-tree)，這里討論1種基于搜索算法的解決方法，其編程復雜性和理解難度略優于LCT做法。
如果每一個節點只有1個值ai,則本題是1道標準的簡單動態計劃：
dp[i]=max(min(dp[j])，ai) map[i][j]=1
可使用spfa或其他最短路算法實現。當每一個節點的值從1個變成2個時，最容易想到的做法是，枚舉其中1個值A，然后用spfa求最小的B，利用A+B更新答案。代碼實現以下：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <set>
#include <vector>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
int n,m,i,j,a,b,best=100001;
struct nod{
int nex,a,b;
};
vector<nod> lin[50005];
int dp[50001],q[50005];
bool vis[50001];
int ans[50001];
int spfa(int a)
{
if (ans[a]!=0) return ans[a];
memset(vis,0,sizeof(vis));
memset(dp,-1,sizeof(dp));
dp[1]=0;
int head,tail;
head=tail=1;
q[1]=1;
vis[1]=1;
int now,xia,b;
nod nex;
while (head<=tail)
{
now=q[head%50003];
vis[now]=0;
for (int j=0;j<lin[now].size();j++)
{
nex=lin[now][j];
xia=nex.nex;
if (nex.a>a) continue;
b=max(dp[now],nex.b);
if (dp[xia]==-1 || b<dp[xia])
{
dp[xia]=b;
if (vis[xia]==0)
{
vis[xia]=1;
tail++;
q[tail%50003]=xia;
}
}
}
head++;
}
if (dp[n]==-1) ans[a]=-1; else ans[a]=dp[n]+a;
if (dp[n]==-1) return -1;
return dp[n]+a;
}
int main()
{
//freopen("1.txt","r",stdin);
memset(ans,0,sizeof(ans));
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) lin[i].clear();
nod temp;
for (int k=1;k<=m;k++)
{
scanf("%d%d%d%d",&i,&j,&a,&b);
//cout<<i<<' '<<j<<endl;
if (i==j) continue;
temp.nex=j; temp.a=a; temp.b=b;
lin[i].push_back(temp);
temp.nex=i;
lin[j].push_back(temp);
}
if (spfa(50000)==-1)
{
cout<<-1<<endl;
return 0;
}
for (int i=1;i<=50000;i++)
{
int temp=spfa(i);
if (temp!=-1) best=min(best,temp);
}
cout<<best<<endl;
}這個做法很容易想到，但極限情況下需要做50000次spfa，只能得到25分，需要斟酌其是不是有優化點。（提交記錄見http://uoj.ac/submission/4830）
優化1：
在起初時，需要枚舉的區間是[1,50000]中的每個A，假定在A=25000時，B=15000。終究答案ans必定滿足ans<=40000，因此，A 在[40000,50000]這個區間不可能產生最優解，可以迅速剪去。同理，假定當前最優解best是30000，由于當A<=25000時，滿足條件A的邊數會比25000時有所減少，B必定會滿足B>=15000， 因此，當A在[30000⑴5000,25000]=[15000,25000]這個區間時，也不可能產生最優解，可以剪去。
利用這個思路，可使用dfs的思想去依照中點的順序枚舉每個節點，思路以下：
1.搜索區間(l,r)，首先對中點mid求其spfa后的結果temp，并更新全局當前最優解best。
2.搜索區間(l,min(mid,best-(temp-mid)))。
3.搜索區間(mid+1,min(r,best))。
實現的進程中需要注意使用dp[i]記錄每個spfa(i)的值，避免重復運算。
int dfs(int l,int r)
{
//cout<<l<<' '<<r<<' '<<best<<endl;
if (l==r)
{
int temp=spfa(l);
if (temp!=-1) best=min(best,temp);
return 0;
}
if (l>r) return 0;
int mid=(l+r)/2;
int temp=spfa(mid);
if (temp==-1)
{
dfs(mid+1,r);
return 0;
}
best=min(best,temp);
//左端點 ll+temp
//A的上限
int lef=best-(temp-mid);
dfs(l,min(lef,mid));
dfs(mid+1,min(r,best));
return 0;
}
加上這個優化后，程序的效力有顯著的提高，可以得到50分。（提交記錄見http://uoj.ac/submission/4831）
優化2：
在spfa的進程中，會枚舉每一個節點i的每條邊，由于存邊的時候是雜亂無序的，因此只能枚舉每一個節點所有的邊。為了優化枚舉的進程，我們可以將每一個節點對應的邊依照a的值從小到大排序，在spfa(a)的進程中，1旦枚舉到某1個大于a的邊時，就break掉，縮小的枚舉的量。這個優化是針對spfa實現進程中的1個優化，但是效果顯著，可以得到70分。（提交記錄見http://uoj.ac/submission/4834）
優化3：
使用了spfa算法實現，當程序效力出現問題時，可以斟酌spfa算法的兩個優化，本處只斟酌其中1種優化。當加入隊尾的節點的距離比當前隊首節點的距離大時，交換兩個節點在隊列中的位置。
if (dp[q[(head+1)%50003]]>dp[q[tail%50003]])
{
swap(q[(head+1)%50003],q[tail%50003]);
}
加上這個優化，本題已獲得97分，耗時3858ms，通過了NOI比賽時的所有正式數據，OJ附加數據中1組超時。（提交記錄見http://uoj.ac/submission/4833）
優化4：
當A變化時，B隨之變化的圖象其實不是連續的，而是1些離散的點，例如：
當A=1,2,3…20時，B=10000，
當A=21,22,23…30時，B=9500，
…
即：當A變化時，B會在某些點產生突變，而不是隨著A的變化連續變化。
那末，對1個搜索區間[l,r]，如果spfa(l)==spfa(r)，則不需要對這個區間進行枚舉了。
在以上基礎上利用此優化，本題中獲得了97分，耗時2063ms，在之前的基礎上效力得到了顯著提升。（提交記錄見http://uoj.ac/submission/4849）
優化5：
在搜索算法不管如何也不能在有限時間求出結果時，可以采取卡時的策略，在程序行將超過時間限制時，停止運算，將當前最優解輸出，有1定幾率得到正確的結果。
修改代碼提交后，本題終究獲得了100分，并通過了附加的多組數據，總耗時1758ms，在（提交記錄見http://uoj.ac/submission/4850）
實際上，本題目在此基礎上還有很多優化，例如：對A，B進行離散化，縮小枚舉的范圍；使用spfa算法的兩個優化；把spfa算法改成最小生成樹等。都可使效力得到提升，請讀者自行嘗試。
/*
AUTHOR:aqx
PROG:魔法森林
LANG:c++
*/
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int cnt=0;
int n,m,i,j,a,b,best=100001;
struct nod{
int nex,a,b;
};
vector<nod> lin[50005];
int dp[50001],q[50005];
bool vis[50001];
int ans[50001];
int cmp(nod x,nod y)
{
return x.a<y.a;
}
inline int spfa(int a)
{
if (ans[a]!=0) return ans[a];
memset(vis,0,sizeof(vis));
memset(dp,-1,sizeof(dp));
dp[1]=0;
int head,tail;
head=tail=1;
q[1]=1;
vis[1]=1;
int now,xia,b;
nod nex;
while (head<=tail)
{
now=q[head%50003];
vis[now]=0;
if (dp[n]!=-1 && dp[now]>=dp[n])
{
head++;
continue;
}
for (int j=0;j<lin[now].size();j++)
{
nex=lin[now][j];
xia=nex.nex;
if (nex.a>a) break;
b=max(dp[now],nex.b);
if (dp[xia]==-1 || b<dp[xia])
{
dp[xia]=b;
if (vis[xia]==0)
{
vis[xia]=1;
tail++;
q[tail%50003]=xia;
if (dp[q[(head+1)%50003]]>dp[q[tail%50003]])
{
swap(q[(head+1)%50003],q[tail%50003]);
}
}
}
}
head++;
}
if (dp[n]==-1) ans[a]=-1; else ans[a]=dp[n]+a;
if (dp[n]==-1) return -1;
return dp[n]+a;
}
int dfs(int l,int r)
{
cnt++;
if (cnt>1000) return 0;
//cout<<l<<' '<<r<<' '<<best<<endl;
if (l==r)
{
int temp=spfa(l);
if (temp!=-1) best=min(best,temp);
return 0;
}
if (l>r) return 0;
int mid=(l+r)/2;
int temp=spfa(mid);
if (temp==-1)
{
dfs(mid+1,min(r,best));
return 0;
}
best=min(best,temp);
//左端點 ll+temp
//A的上限
int lef=best-(temp-mid);
if (spfa(l)-l!=spfa(mid)-mid) dfs(l,min(lef,mid));
else
{
int temp=spfa(l);
if (temp!=-1) best=min(best,temp);
}
if (spfa(r)-r!=spfa(mid)-mid) dfs(mid+1,min(r,best));
return 0;
}
int main()
{
int zuida=0;
//freopen("1.txt","r",stdin);
memset(ans,0,sizeof(ans));
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) lin[i].clear();
nod temp;
for (int k=1;k<=m;k++)
{
scanf("%d%d%d%d",&i,&j,&b,&a);
//cout<<i<<' '<<j<<endl;
if (i==j) continue;
zuida=max(zuida,a);
temp.nex=j; temp.a=a; temp.b=b;
lin[i].push_back(temp);
temp.nex=i;
lin[j].push_back(temp);
}
for (int i=1;i<=n;i++)
{
sort(lin[i].begin(),lin[i].end(),cmp);
}
if (spfa(50000)==-1)
{
cout<<-1<<endl;
return 0;
}
dfs(1,zuida);
cout<<best<<endl;
}
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
