待续。。。官方题解

前言：这场比赛打得非常坎坷，刚开始以为7:30开始，结果迟进赛场。然后因为是在家里打，键盘好难用啊=_= 哔——地一声，电脑关机，发现充电线没插好。。。插好之后，肚子饿->去翻柜子吃东西，所以解题速度就变成这样了？！

A

DP

B

水水的二分题，我竟然在二分判断可行解时用了tarjan，虽然也卡过去了，但明显用拓扑序更优

C

其实就是先将已确定的边相连，同时求出所有边相连后的联通块/生成树个数（并查集维护）s1 遍历之前由确定的边相连所得到的森林，并判断是否已有矛盾，同时标记颜色。求出当前的联通块/生成树个数s2 则2^(s2-s1)即为答案，自己模拟下应该就能理解

题解 #include<bits/stdc++.h> #define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++) #define per(i,j,k) for(int i=(int)j;i>=(int)k;i--) #define pii pair<int,int> using namespace std; typedef long long LL; typedef double db; const int N=110000; const int P=998244353; int n,m; int head[N],np[N<<1],p[N<<1],col[N<<1],tot; int w[N],fa[N]; bool wei=0; inline int get(int x){if(x==fa[x])return x;return fa[x]=get(fa[x]);} int kk=0; void dfs(int x,int c){ w[x]=c; if(wei)return; for(int u=head[x];u;u=np[u]){ int y=p[u]; int d=col[u]; if(w[y]==-1)dfs(y,c^d); else{ if((w[x]^w[y])!=d)wei=1; } } } int main(){ scanf("%d%d",&n,&m); rep(i,1,n)fa[i]=i;kk=n; rep(i,1,m){ int a,b,c;scanf("%d%d%d",&a,&b,&c); if(get(a)^get(b)){ fa[get(a)]=get(b); --kk; } if(c==-1)continue; ++tot;p[tot]=b;np[tot]=head[a];head[a]=tot;col[tot]=c; ++tot;p[tot]=a;np[tot]=head[b];head[b]=tot;col[tot]=c; } memset(w,-1,sizeof w); int rp=0; rep(i,1,n)if(w[i]==-1){ dfs(i,0); ++rp; } if(wei){ printf("0\n"); return 0; } int ans=1; cerr<<rp<<" "<<kk<<endl; rep(i,1,rp-kk)ans=ans*2ll%P; printf("%d\n",ans); return 0; }

转载于:https://www.cnblogs.com/MikuKnight/p/9282050.html

相关资源：JAVA上百实例源码以及开源项目