lightoj 1251 (Two_Sat)

时间:2023-03-10 03:17:00
lightoj 1251 (Two_Sat)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std; const int maxn = ;
const int INF = 0x3f3f3f; int n,m;
char a[maxn][];
int b[maxn][]; struct TwoSat{
int n;
vector<int> G[maxn*];
bool mark[*maxn];
int s[*maxn],cnt; void init(int n){
this->n = n;
memset(mark,,sizeof(mark));
for(int i=;i<=*n;i++) G[i].clear();
} void add_clause(int u,int uval,int v,int vval){
u = u* + uval; //u,v有矛盾;
v = v* + vval;
G[u].push_back(v^);
G[v].push_back(u^);
} bool dfs(int u){
if(mark[u^]) return false;
if(mark[u]) return true;
mark[u] = true;
s[cnt++] = u; //记录你所选择的路径;
for(int i=;i<G[u].size();i++ ){
if( !dfs(G[u][i]) ) return false;
}
return true;
} bool solve(){
for(int i=;i<*n;i+=){
if(!mark[i] && !mark[i+]){
cnt = ;
if(!dfs(i)){
while(cnt > ) mark[s[--cnt]] = false;
if(!dfs(i+)) return false;
}
}
}
return true;
}
void print(){
int ans[maxn],pv = ;
for(int i=;i<*n;i+=){
if(mark[i] && a[i/][] == '+'){
ans[pv++] = b[i/][];
}
else if(mark[i+] && a[i/][] == '+'){
ans[pv++] = b[i/][];
}
}
sort(ans,ans+pv);
int num = unique(ans,ans+pv) - ans;
printf("%d",num);
for(int i=;i<num;i++) printf(" %d",ans[i]);
printf("\n");
} }solver; int main()
{
//freopen("E:\\acm\\input.txt","r",stdin);
int T;
cin>>T;
for(int t=;t<=T;t++){
scanf("%d %d",&n,&m);
solver.init(n);
vector<int> p1[],p2[],n1[],n2[];
for(int i=;i<n;i++){
int temp;
scanf("%c%c%d%c%c%d",&temp,&a[i][],&b[i][],&temp,&a[i][],&b[i][]);
if(a[i][] == '+'){
p1[b[i][]].push_back(i);
p2[b[i][]].push_back();
}
else{
n1[b[i][]].push_back(i);
n2[b[i][]].push_back();
}
if(a[i][] == '+'){
p1[b[i][]].push_back(i);
p2[b[i][]].push_back();
}
else{
n1[b[i][]].push_back(i);
n2[b[i][]].push_back();
}
}
for(int i=;i<=m;i++){
for(int j=;j<p1[i].size();j++)
for(int k=;k<n1[i].size();k++){
solver.add_clause(p1[i][j],p2[i][j],n1[i][k],n2[i][k]);
}
}
if(solver.solve()){
printf("Case %d: Yes\n",t);
solver.print();
}
else printf("Case %d: No\n",t);
}
}

题目链接:http://lightoj.com/volume_showproblem.php?problem=1251