因?yàn)樘酪恢睂慣1也沒(méi)仔細(xì)想，賽后發(fā)現(xiàn)是個(gè)真小清新思維題，本質(zhì)構(gòu)造？？？

首先顯然不會(huì)無(wú)解，這個(gè)隨隨便便證一下就有了

另外給的式子沒(méi)啥意義，也就能說(shuō)明顏色隨機(jī)？？？害人不淺

然后就從\(1\)開始，欽點(diǎn)顏色為\(0\)，然后順著編號(hào)遞增判斷能不能同色入棧，不能則彈出棧頂元素，如果彈空了則意味著當(dāng)前點(diǎn)和其他點(diǎn)都有顏色為\(1\)的邊，于是這樣跑就能得到解，時(shí)間復(fù)雜度\(\mathcal{O}(n\log n)\)（\(\log\)是因?yàn)橛昧薽ap）

#include<bits/stdc++.h> #define pii pair<int,int> #define mk make_pair #define fi first #define se second #define pb push_back typedef long long ll;using namespace std;const int N=5e5+5;void qread(int &xx){xx=0;int ch=getchar();while(ch<'0'||ch>'9'){ch=getchar();}while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();} }void qread(ll &xx){xx=0;int ch=getchar();while(ch<'0'||ch>'9'){ch=getchar();}while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();} }map<int,int>G[N];vector<pii>ans[2];stack<int>st;int n,m,col;long long X,Y,Z,p[N];int query(int u,int v){if(G[u].count(v)){return G[u][v];}return (1LL*(u<v?u:v)*X+1LL*(u>v?u:v)*Y)%Z>=p[u]+p[v]; }void solve(){st.push(1);for(int i=2;i<=n;i++){while(!st.empty()){int u=st.top(),ec=query(u,i);ans[ec].pb(mk(u,i));if(col^ec){st.pop();}else{break;}}if(st.empty()){col^=1;st.push(1);}st.push(i);} }int main(){qread(n);qread(m);for(int i=1,u,v,w;i<=m;i++){qread(u);qread(v);qread(w);G[u][v]=G[v][u]=w;}qread(X);qread(Y);qread(Z);for(int i=1;i<=n;i++){qread(p[i]);}solve();for(auto pr:ans[col]){printf("%d %d\n",pr.fi,pr.se);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/--BLUESKY007/p/11144808.html

總結(jié)

以上是生活随笔為你收集整理的noi.ac NA535 【生成树】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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