正解思路，感覺應該是先判特殊情況，比如新建的路線可以建在于1-n無關的地方，具體判別方法見代碼

然后再判斷舊路線兩端的最大貢獻值，即代碼中的ans，枚舉1-n線路中的每個節(jié)點i，求1-[1,i]節(jié)點的最大值和[i+1,n]-n節(jié)點的最大值，維護ans即可

?

#include<iostream> #include<cstdio> #include<cmath> #include<queue> #include<vector> #include<string.h> #include<cstring> #include<algorithm> #include<set> #include<map> #include<fstream> #include<cstdlib> #include<ctime> #include<list> #include<climits> using namespace std; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout); #define scd(a) scanf("%d",&a) #define scf(a) scanf("%lf",&a) #define scl(a) scanf("%lld",&a) #define sci(a) scanf("%I64d",&a) #define scs(a) scanf("%s",a) #define left asfdasdasdfasdfasfasdfasfsdfasfdas typedef long long ll; const int desll[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; const ll mod=1e9+7; const int maxn=3e5+7; const int maxm=1e8+7; const double eps=1e-4; int m,n; int ar[maxn]; set<pair<ll,int> > se1,se2; pair<int,pair<ll,int> > pal1[maxn],pal2[maxn]; int le1,le2; vector<pair<int,int> > e[maxn]; int markl[maxn],mark; set<pair<int,int> > seMa; ll ans=0,ansMid; int ansl[maxn]; void dfs(int u,int pre) {if(u==n){mark=1;markl[u]=1;return ;}for(int i=0;i<e[u].size();i++){int v=e[u][i].first;if(v==pre)continue;dfs(v,u);if(mark){markl[u]=1;return ;}} } void dfs1(int u,int pre,ll sum,int ins) {pal1[le1].first=ins;pal1[le1].second.first=sum;pal1[le1++].second.second=u;if(u==n){ansMid=sum;}for(int i=0;i<e[u].size();i++){int v=e[u][i].first;if(v==pre)continue;dfs1(v,u,sum+e[u][i].second,ins+markl[v]);} } void dfs2(int u,int pre,ll sum,int ins) {pal2[le2].first=ins;pal2[le2].second.first=sum;pal2[le2++].second.second=u;for(int i=0;i<e[u].size();i++){int v=e[u][i].first;if(v==pre)continue;dfs2(v,u,sum+e[u][i].second,ins+markl[v]);} } int main() {scd(n);scd(m);for(int i=1;i<n;i++){int a,b,c;scd(a);scd(b);scd(c);e[a].push_back(make_pair(b,c));e[b].push_back(make_pair(a,c));seMa.insert(make_pair(a,b));seMa.insert(make_pair(b,a));}memset(markl,0,sizeof(markl));mark=0;le1 = le2 = 0;ans=0,ansMid=0;dfs(1,0);//求1-n所經(jīng)過的各個節(jié)點dfs1(1,0,0,0);dfs2(n,0,0,0);sort(pal1,pal1+le1);sort(pal2,pal2+le2);for(int i=1;i<=n;i++){//看新建線路能否建在與1-n無關的地方，若能，其實后面的while維護ans可省略int ins=0;if(markl[i]){for(int j=0;j<e[i].size();j++){int x=e[i][j].first;if(markl[x]==0)ins++;}}else{ins=e[i].size();}if(ins>=2){ans=ansMid;break;}}int maxNum=pal1[le1-1].first;int be=0;for(int i=0;i<le2;i++){if(pal2[i].first==maxNum)break;se2.insert(pal2[i].second);be=i;}int ins=0,res=0;while(res<maxNum){//維護answhile(pal1[ins].first<=res){se1.insert(pal1[ins].second);ins++;}auto au1=se1.end();auto au2=se2.end();au1--;au2--;if(seMa.count(make_pair(au1->second,au2->second))){//若兩個節(jié)點本身相連，即都在1-n的主線路上，則需退一步判次大值if(au1!=se1.begin()){au1--;ans = max(ans, au1->first+au2->first);au1++;}if(au2!=se2.begin()){au2--;ans = max(ans, au1->first+au2->first);au2++;}}else ans = max(ans, au1->first+au2->first);res++;while(pal2[be].first+res==maxNum){se2.erase(pal2[be].second);be--;}}//cout<<maxNum<<" "<<ansMid<<" "<<ans<<endl;for(int i=0;i<m;i++){int ins;scd(ins);printf("%I64d\n",min(ansMid,ans+ins));}return 0; }

?

轉載于:https://www.cnblogs.com/wa007/p/9445025.html

總結

以上是生活随笔為你收集整理的Codeforces 1016FRoad Projects的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。