CF1039C Network Safety

題意：

題解：

如果我們同時選中a，b兩個點，無論異或什么值，都不會影響圖的安全性，因為圖本來就是安全的
破壞圖的安全性只有一種情況，那就是選了a，沒選b，且病毒為x，滿足a⊕x=b
根據異或的性質，x=a⊕b，那么也就說要讓圖不安全的方法就是只選兩個端點中的一個且病毒x為兩個端點的異或值。
那么當病毒x=a⊕b時，我們就一定要選AB兩點，我們把AB看做一個點，這樣我們將相同邊權的看作點，且合并起來
如果合并完后有k個點，說明這k個點之間的異或值都不為x，也就是這k個點可以隨便選，有$2^k$個選擇
我們可以用并查集來處理合并點
在實踐中，我們先不考慮不安全的情況，求出總方案，然后每次合并一個點后，減去不合法的情況

代碼：

#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } 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'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime = clock ();freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int mod=1e9+7; const int maxn=5e5+9; map<ll,int>a; map<ll,bool>mp; ll b[maxn]; map<ll,int>fa[maxn]; int u[maxn],v[maxn]; int find(int x,ll key){if(fa[x][key]==x)return x;return fa[x][key]=find(fa[x][key],key); } ll poww(ll a,ll b) {ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans%mod; } int main() {//rd_test();int n,m,k;read(n,m,k);ll ans=0;ans=poww(2,k)*poww(2,n)%mod; // cout<<ans<<endl;for(int i=1;i<=n;i++)read(b[i]);for(int i=1;i<=m;i++){read(u[i],v[i]);ll key=b[u[i]]^b[v[i]];if(fa[u[i]][key]==0)fa[u[i]][key]=u[i];if(fa[v[i]][key]==0)fa[v[i]][key]=v[i];int x=find(u[i],key);int y=find(v[i],key);if(x==y)continue;fa[x][key]=y;a[key]++;//去掉了不合法的情況 ll w=(poww(2,n-(a[key]-1))-poww(2,n-a[key])+mod)%mod;ans=(ans-w+mod)%mod;}cout<<ans%mod;return 0;//Time_test(); }

總結

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

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