題目鏈接：https://vjudge.net/problem/CodeForces-1494E

題目大意：給出一個初始時只有 $n$ 個點的有向帶權圖，需要執行 $m$ 次操作，每次操作分為下列三種類型：

$+uvc$：增加一條 $u?>v$ 的有向邊，邊權為 $c$

$?uv$：刪除 $u?>v$ 的有向邊

$?k$：檢查是否存在著一條路徑經過了 $k$ 個點（可以重復），滿足 $a_1?>a_2?>...?>a_k$ 存在著一條路徑且 $a_k?>a_{k?1}?>...?>a_2?>a_1$ 也存在著一條路徑，且兩條路徑的邊權組成的序列相同

題目保證每次操作都是合法的

題目分析：看到上面的條件需要分析環，因為題目中不會出現自環，所以最簡單的環就是 $u?>v$ 且 $v?>u$ 這樣的一個環了

假設存在著這樣的一個環，那么對于每次操作三，當 $k$ 為奇數的時候，一定可以從 $u$ 或 $v$ 出發然后回到自身，所以如果存在著環，無論邊權，答案都是可以構造出來的

那么當 $k$ 為偶數的情況，依然沿著環走的話，會變成以 $u$ 為起點，且以 $v$ 為終點的情況，也就是說正著的路徑為 $uvuv....v$，反著的路徑為 $vuvu...u$，如果要想讓這兩條路徑的序列相等的話，必須要滿足 $u?>v$ 和 $v?>u$ 這兩條路徑的權值相等才行

這樣一來只需要維護這樣的環是否存在即可，代碼實現起來也比較簡單

代碼：

// Problem: E. A-Z Graph // Contest: Codeforces - Educational Codeforces Round 105 (Rated for Div. 2) // URL: https://codeforces.com/contest/1494/problem/E // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; char s[N]; map<pair<int,int>,char>mp; set<pair<int,int>>diff,equ; void add_diff(int u,int v) {if(u>v) {swap(u,v);}diff.insert({u,v}); } void add_equ(int u,int v) {if(u>v) {swap(u,v);}equ.insert({u,v}); } void del_diff(int u,int v) {if(u>v) {swap(u,v);}diff.erase({u,v}); } void del_equ(int u,int v) {if(u>v) {swap(u,v);}equ.erase({u,v}); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;read(n),read(m);while(m--) {string op;cin>>op;if(op=="+") {int u,v;read(u),read(v);scanf("%s",s+1);mp[{u,v}]=s[1];if(mp[{v,u}]!=0) {if(mp[{v,u}]==s[1]) {add_equ(u,v);} else {add_diff(u,v);}}} else if(op=="-") {int u,v;read(u),read(v);if(mp[{v,u}]!=0) {if(mp[{v,u}]==mp[{u,v}]) {del_equ(u,v);} else {del_diff(u,v);}}mp[{u,v}]=0;} else if(op=="?") {int k;read(k);if(k&1) {if(diff.size()||equ.size()) {puts("YES");} else {puts("NO");}} else {if(equ.size()) {puts("YES");} else {puts("NO");}}}}return 0; }

總結

以上是生活随笔為你收集整理的CodeForces - 1494E A-Z Graph(构造+思维)的全部內容，希望文章能夠幫你解決所遇到的問題。

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