[cf553C]Love Triangles

待我称王封你为后i 2021-11-17 15:32 223阅读 0赞

题意可以理解为加边使原图变为完全图后不含有偶环的方案数（边权为0或1），可以联想到二分图染色，询问完全图的方案数即询问对于每一个点可以选0或1，然后使得1边连接的两点点权相同，0边连接的两点点权不同。

对于第一个联通块，显然已经确定，然后从第一个联通块向每一个联通块中的某一点连0边或1边都可以确定该联通块，所以答案等于$2^\{联通块数-1\}$（注意若初始不合法，答案为0）。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 #define mod 1000000007
     4 #define N 100005
     5 struct ji{
     6     int nex,to,len;
     7 }edge[N<<1];
     8 int E,n,m,x,y,z,ans,head[N],a[N];
     9 void add(int x,int y,int z){
    10     edge[E].nex=head[x];
    11     edge[E].to=y;
    12     edge[E].len=z;
    13     head[x]=E++;
    14 }
    15 bool dfs(int k,int sh){
    16     if (a[k]>=0)return a[k]==sh;
    17     a[k]=sh;
    18     for(int i=head[k];i!=-1;i=edge[i].nex)
    19         if (!dfs(edge[i].to,sh^edge[i].len^1))return 0;
    20     return 1;
    21 }
    22 int main(){
    23     scanf("%d%d",&n,&m);
    24     memset(head,-1,sizeof(head));
    25     memset(a,-1,sizeof(a));
    26     ans=mod/2+1;
    27     for(int i=1;i<=m;i++){
    28         scanf("%d%d%d",&x,&y,&z);
    29         add(x,y,z);
    30         add(y,x,z);
    31     }
    32     for(int i=1;i<=n;i++)
    33         if (a[i]<0)
    34             if (!dfs(i,0))ans=0;
    35             else ans=ans*2%mod;
    36     printf("%d",ans);
    37 }

转载于:https://www.cnblogs.com/PYWBKTDA/p/11254599.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211116/a7d95258cab1420490df8850f06592b5.png