2 条题解
-
0
#include <bits/stdc++.h> using namespace std; const int N = 2100; vector<int> G[N]; int n, m; int tsp, cnt, dfn[N], low[N], scc[N]; stack<int> stk;bool instk[N]; void tarjan(int x) { dfn[x] = low[x] = ++tsp; stk.push(x); instk[x] = true; for(int y : G[x]) { if(!dfn[y]) { tarjan(y); low[x] = min(low[x], low[y]); } else if(instk[y]) low[x] = min(low[x], dfn[y]); } if(dfn[x] == low[x]) { cnt++; for(int z = -1; z != x;) { z = stk.top(); stk.pop(); instk[z] = false; scc[z] = cnt; } } } int main() { scanf("%d%d", &n, &m); for(int i = 1, x, y, c; i <= m; i++) { scanf("%d%d%d", &x, &y, &c); char ss[10]; scanf("%s", ss); //设节点 a 表示变量 x[a]赋值为 0，节点 a + N 表示变量 x[a]赋值为 1。 if(ss[0] == 'A') { if(c == 1) G[x].push_back(x + n), G[y].push_back(y + n); else G[x + n].push_back(y), G[y + n].push_back(x); /*1. a and b = 1 这表示 x[a], x[ b ]两个变量都必须赋值为 1，该关系可由 2 条有向边描述: 若 x[a] = -0，则必须 x[a] = 1，从 a 到 a + N连有向边(若将来选择了x[a+n](表示x[a]=1)，经过一条链能够推导到x[a](x[a]=0)因为x[a]->x[a+n]这条边的存在而形成一个scc) 若 x[ b ] = 0，则必须 x[ b ] = 1，从 b 到 b + N 连有向边 2.a and b = 0 这表示 x[a], x[ b ]其中一个赋值为 1 时，另一个必须赋值为 0 if x[a] = 1，则必须 x[ b ] = -0从 a + N 向 b 连有向边 若 x[ b ] = 1，则必须 x[a] = 0，从 b + N 向 a 连向边*/ } else if(ss[0] == 'O') { if(c == 1) G[x].push_back(y + n), G[y].push_back(x + n); else G[x + n].push_back(x), G[y + n].push_back(y); /*3. a or b = 1 这表示 x[a], x[ b ]其中一个赋值为 0 时，另一个必须赋值为 1 若 x[a] = 0，则必须 x[ b ] = 1，从 a 向 b + N 连有向边 若 x[ b ] = 0，则必须 x[a] = 1，从 b 向 a + N 连有向边 4. a or b = 0 这表示 x[a], x[ b ]两个变量都必须赋值为 0，该关系可由 2 条有向边描述——若赋值为 1，让它直接产生矛盾即可。 若 x[a] = -1，则必须 x[a] = 0，从 a + N 到 a 连有向边 若 x[ b ] = 1，则必须 x[ b ] = 0，从 b + N 到 b 连有向边*/ } else //if(ss[0] == 'X') { if(c == 1) G[x + n].push_back(y), G[y + n].push_back(x), G[x].push_back(y + n), G[y].push_back(x + n); else G[x + n].push_back(y + n), G[y + n].push_back(x + n), G[x].push_back(y), G[y].push_back(x); /*5. a xor b = 1 这表示 x[a], x[ b ]两个变量必须不相等 若 x[a] = 1，则必须 x[ b ] =0，从 a + N 向 b 连有向边 若 x[ b ] = 1，则必须 x[a] =0，从 b + N 向 a 连有向边 若 x[a] =0，则必须 x[ b ] =1，从 a 向 b + N 连有向边 若 x[ b ] =0，则必须 x[a] =1，从 b 向 a + N 连有向边 6. a xor b = 0 这表示 x[a], x[ b ]两个变量必须相等 若 x[a] =1，则必须 x[ b ] =1，从 a + N 向 b + N 连有向边 若 x[ b ] =1，则必须 x[a] =1，从 b + N 向 a + N 连有向边 若 x[a] =0，则必须 x[ b ] =0，从 a 向 b 连有向边 若 x[ b ] =0，则必须 x[a] =0，从 b 向 a 连有向边*/ } } //根据以上的规则来建图，然后用 Tarjan 求出所有强连通分量， //若存在任意 a 和 a + N 在同一强连通分量中，说明无解，否则有解 tsp = cnt = 0; memset(low, 0, sizeof(low)); memset(dfn, 0, sizeof(dfn)); memset(instk, 0, sizeof(instk));//初始化所有变量 for(int i = 1; i <= 2 * n; i++) if(!dfn[i]) tarjan(i); //对每个未访问节点进行tarjan for(int i = 1; i <= n; i++) if(scc[i] == scc[i + n]) {puts("NO"); return 0;} //检查是否有变量x[i]和x[i]+N在同一scc puts("YES"); return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 16:57:03
#include<bits/stdc++.h> using namespace std; const int N=2100; vector<int>G[N]; int n, m; int tsp, cnt, dfn[N], low[N], scc[N]; stack<int>stk;bool instk[N]; void tarjan(int x) { dfn[x]=low[x]=++tsp; stk.push(x);instk[x]=True; for(int y:G[x]) { if(!dfn[y]) { tarjan(y); low[x]=min(low[x], low[y]); } else if(instk[y]) low[x]=min(low[x], dfn[y]); } if(dfn[x]==low[x]) { cnt++; for(int z=-1;z!=x;) { z=stk.top(); stk.pop(); instk[z]=False; scc[z]=cnt; } } } int main() { scanf("%d%d", &n, &m); for(int i=1,x,y,c;i<=m;i++) { scanf("%d%d%d", &x,&y,&c); char ss[10]; scanf("%s", ss); //设节点 a 表示变量 x[a] 赋值为 0，节点 a + N 表示变量 x[a] 赋值为 1。 if(ss[0]=='A') { if(c==1) G[x].push_back(x+n), G[y].push_back(y+n); else G[x+n].push_back(y), G[y+n].push_back(x); /*1. a and b = 1 这表示 x[a], x[ b ]两个变量都必须赋值为 1，该关系可由 2 条有向边描述: 若 x[a] = 0，则必须 x[a] = 1，从 a 到 a + N 连有向边 (若将来选择了x[a+n](表示x[a]=1) ，经过一条链能够推导到 x[a](x[a]=0),因为 x[a]->x[a+n]这条边的存在而形成一个scc) 若 x[ b ] = 0，则必须 x[ b ] = 1，从 b 到 b + N 连有向边 2. a and b = 0 这表示 x[a], x[ b ] 其中一个赋值为 1 时，另一个必须赋值为 0 若 x[a] = 1，则必须 x[ b ] = 0，从 a + N 向 b 连有向边 若 x[ b ] = 1，则必须 x[a] = 0，从 b + N 向 a 连有向边*/ } else if(ss[0]=='O') { if(c==1) G[x].push_back(y+n),G[y].push_back(x+n); else G[x+n].push_back(x),G[y+n].push_back(y); /* 3. a or b = 1 这表示 x[a], x[ b ] 其中一个赋值为 0 时，另一个必须赋值为 1 若 x[a] = 0，则必须 x[ b ] = 1，从 a 向 b + N 连有向边 若 x[ b ] = 0，则必须 x[a] = 1，从 b 向 a + N 连有向边 4. a or b = 0 这表示 x[a], x[ b ] 两个变量都必须赋值为 0，该关系可由 2 条有向边描述——若赋值为 1，让它直接产生矛盾即可。 若 x[a] = 1，则必须 x[a] = 0，从 a + N 到 a 连有向边 若 x[ b ] = 1，则必须 x[ b ] = 0，从 b + N 到 b 连有向边*/ } else //if(ss[0]=='X') { if(c==1) G[x+n].push_back(y),G[y+n].push_back(x),G[x].push_back(y+n),G[y].push_back(x+n); else G[x+n].push_back(y+n),G[y+n].push_back(x+n),G[x].push_back(y),G[y].push_back(x); /*5. a xor b = 1 这表示 x[a], x[ b ] 两个变量必须不相等 若 x[a] = 1，则必须 x[ b ] = 0，从 a + N 向 b 连有向边 若 x[ b ] = 1，则必须 x[a] = 0，从 b + N 向 a 连有向边 若 x[a] = 0，则必须 x[ b ] = 1，从 a 向 b + N 连有向边 若 x[ b ] = 0，则必须 x[a] = 1，从 b 向 a + N 连有向边 6. a xor b = 0 这表示 x[a], x[ b ] 两个变量必须相等 若 x[a] = 1，则必须 x[ b ] = 1，从 a + N 向 b + N 连有向边 若 x[ b ] = 1，则必须 x[a] = 1，从 b + N 向 a + N 连有向边 若 x[a] = 0，则必须 x[ b ] = 0，从 a 向 b 连有向边 若 x[ b ] = 0，则必须 x[a] = 0，从 b 向 a 连有向边*/ } } //根据以上的规则来建图，然后用 Tarjan 求出所有强连通分量， //若存在任意 a 和 a + N 在同一强连通分量中，说明无解，否则有解 tsp=cnt=0;memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));memset(instk,0,sizeof(instk)); for(int i=1;i<=2*n;i++) if(!dfn[i]) tarjan(i); for(int i=1;i<=n;i++) if(scc[i]==scc[i+n]) {puts("NO"); return 0;} puts("YES"); return 0; }
- 1
