题目传送门
题意：有一个 n 个点的无向完全图，边权为 0/1，钦定 m 条边的边权，求填剩下的边的边权的方案数，满足：不存在一个三元环全为 0 或二 1 一 0。
观察第二条性质。首先显然有，如果 a−b,b−c 为 1，则 a−c 为 1，所以 1 的关系具有传递性：只要两个点在同一个 1 的连通块内，这两点之间也必然为 1。于是每个 1 的连通块必为一个边权全为 1 的完全图。于是，可以先处理钦定的边权为 1 的边，用并查集维护，对于一个钦定边权为 0 的边，如果两边连通则无解。
处理完后，一定维护出若干个由 1 连接的连通块，以及一些连接两个连通块的 0 边。连通块内部肯定边权全为 1，所以只需要考虑连通块之间的。容易发现，两个连通块只要连了一条 1 的边，则合并成一个连通块，所以两个连通块之间的所有边必须全设成 1。也就是说，两个连通块之间有钦定 0 边，则一定不能合并。否则一定可以合并。最终状态一定为，合并成若干个全 1 的连通块，且这些连通块之间全为 0。
研究完第二个限制，考虑第一个限制：不存在三元环全为 0。这说明连通块个数不能超过两个。于是，对于一条钦定权值为 0（即不能合并）的边，两个端点必然在不同的连通块内，相同连通块内不能出现这种边。于是抽象成二分图。
具体地，首先将全为 1 的完全图连通块缩成点，然后用钦定 0 的进行连边，则形成的图必须为二分图（否则无解）。DFS 或并查集匹配一下即可。对于方案数，每个连通块缩成的点有左右两种对称的放置方式，所以答案为 2cnt。由于每种方案还有一种完全对称的方案，而我们只考虑点集分配方式，左右没有区分，所以答案再除以 2。
By cxm1024
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
struct node{int x,y,z;} a[100010];
int fa[100010];
int findf(int x) {
if(x==fa[x]) return x;
return fa[x]=findf(fa[x]);
}
vector<int> e[100010];
int col[100010],vis[100010];
void dfs(int now,bool color) {
if(vis[now]&&color!=col[now]) {
cout<<0<<endl;
exit(0);
}
if(vis[now]) return;
vis[now]=1,col[now]=color;
for(int v:e[now]) dfs(v,!color);
}
signed main() {
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
cin>>a[i].x>>a[i].y>>a[i].z;
for(int i=1;i<=m;i++)
if(a[i].z==1&&findf(a[i].x)!=findf(a[i].y))
fa[findf(a[i].x)]=findf(a[i].y);
for(int i=1;i<=m;i++) {
if(a[i].z==1) continue;
if(findf(a[i].x)==findf(a[i].y)) {
cout<<0<<endl;
return 0;
}
e[findf(a[i].x)].push_back(findf(a[i].y));
e[findf(a[i].y)].push_back(findf(a[i].x));
}
int ans=(mod+1)/2;
for(int i=1;i<=n;i++)
if(findf(i)==i&&!vis[i])
dfs(i,0),(ans*=2)%=mod;
cout<<ans<<endl;
return 0;
}
|