傳送門
文章目錄
題意：
給你一張nnn個點mmm個邊的圖，mmm條邊是給定的，要求你給未給定的邊賦值一個邊權，使得所有邊權異或和為000，求所有滿足這種情況的圖中最小生成樹邊權和最小的，輸出最小生成樹的邊權和。
思路
我們先假設多余的邊邊權都為000，已經有的邊的異或和為sumxorsum_{xor}sumxor?，加上多余的邊跑最小生成樹后如果還有多余的邊不在生成樹中，那么答案顯然為當前MSTMSTMST的權值，因為我們可以選一條不在MSTMSTMST中的邊讓他的權值為sumxorsum_{xor}sumxor?。否則多余的邊都在生成樹里，那么一個最優的情況一定是選出一條多余的邊使其邊權為sumxorsum_{xor}sumxor?，其他的邊權為000。
那么我們拿出來多余的邊，即原圖的補圖，找到補圖中所有的聯通塊，之后再用本來就有的邊將聯通塊聯通，當前的答案為ansansans，現在我們需要判斷一下是否有多余的邊剩下，這個可以算一下rest=n?(n?1)2?mrest=\frac{n*(n-1)}{2}-mrest=2n?(n?1)??m，讓后每加一條邊就讓rest??rest--rest??，最后看看是否rest>0rest>0rest>0即可，如果剩下了直接輸出ansansans，否則我們需要找到一條多余的邊使其邊權為sumxorsum_{xor}sumxor?，我們可以枚舉原圖的邊，來判斷一下能否用原圖中的邊替代來讓答案邊的更小，注意我們上面連接補圖的聯通塊的邊不能被替代。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
,m
;
int p
[N
];
LL rest
,xr
;
bool st
[N
];
set
<int>v
[N
],all
;
struct Node
{int a
,b
,w
,flag
; bool operator < (const Node
&W
) const {return w
<W
.w
;}
}edge
[N
];int find(int x
) {return x
==p
[x
]? x
:p
[x
]=find(p
[x
]);
}void get_block() {queue
<int>q
;vector
<int>now
;for(int i
=1;i
<=n
;i
++) {if(!st
[i
]) {q
.push(i
); st
[i
]=1;all
.erase(i
);while(q
.size()) {int u
=q
.front(); q
.pop();now
.clear();for(auto x
:all
) {if(v
[u
].count(x
)) continue;q
.push(x
); now
.pb(x
);st
[x
]=1; p
[x
]=u
;rest
--;}for(auto x
:now
) all
.erase(x
);}}}
}int main()
{
cin
>>n
>>m
;rest
=1ll*n
*(n
-1)/2-m
;for(int i
=1;i
<=n
;i
++) all
.insert(i
),p
[i
]=i
;for(int i
=1;i
<=m
;i
++) {int a
,b
,c
; scanf("%d%d%d",&a
,&b
,&c
);edge
[i
]={a
,b
,c
,0};v
[a
].insert(b
); v
[b
].insert(a
);xr
^=c
;}get_block();sort(edge
+1,edge
+1+m
);LL ans
=0;for(int i
=1;i
<=m
;i
++) {int a
=edge
[i
].a
,b
=edge
[i
].b
,w
=edge
[i
].w
;a
=find(a
); b
=find(b
);if(a
==b
) continue;p
[a
]=b
; ans
+=w
; edge
[i
].flag
=1;}if(rest
>0) {printf("%lld\n",ans
);return 0;}for(int i
=1;i
<=n
;i
++) p
[i
]=i
;for(int i
=1;i
<=m
;i
++) {int a
=edge
[i
].a
,b
=edge
[i
].b
,w
=edge
[i
].w
;a
=find(a
); b
=find(b
);if(a
==b
) continue;p
[a
]=b
; if(!edge
[i
].flag
) xr
=min(xr
,1ll*w
);}printf("%lld\n",ans
+xr
);return 0;
}
總結
以上是生活随笔為你收集整理的Codeforces Round #715 (Div. 1) C. Complete the MST 补图 + 思维 + 最小生成树的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
