首页 > 代码库 > Ural 1382 2SAT
Ural 1382 2SAT
ural1382 直接套用 2SAT模板
缩点 拓扑排序。。。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<vector> #include<queue> #include<stack> #include<algorithm> //2SAT问题 准确判断矛盾边 不必考虑推出的边是否存在矛盾!! using namespace std; const int maxn=(1000+1); vector<int>po[maxn*2],ps[maxn*2],strong[maxn*2]; bool vis[maxn*2],added[maxn*2][maxn*2]; int n,a[maxn],b[maxn],c[maxn],tot=0,color[maxn*2],du[maxn*2],point[maxn*2]; stack<int>s; void add(int b,int a) { if(added[b][a])return; else added[b][a]=true; po[a].push_back(b); ps[b].push_back(a); } void dfs1(int cur,int fa) { vis[cur]=true; for(int i=0;i<po[cur].size();i++) { int np=po[cur][i]; if(np==fa||vis[np])continue; dfs1(np,cur); } s.push(cur); } void dfs2(int cur,int co,int fa) { strong[co].push_back(cur); color[cur]=co; for(int i=0;i<ps[cur].size();i++) { int np=ps[cur][i]; if(np==fa||(color[np]))continue; dfs2(np,co,cur); } } void strongconnect() { memset(vis,0,sizeof(vis));memset(color,0,sizeof(color)); for(int i=1;i<=n*2;i++) if(!vis[i])dfs1(i,-1); tot=1; while(!s.empty()) { int np=s.top(); s.pop(); if(color[np])continue; dfs2(np,tot++,-1); } } bool cmp(int a,int b) { return du[a]<du[b]; } int topo(int ans[]) { for(int i=1;i<tot;i++) point[i]=i; bool anss=1; for(int i=1;i<tot;i++) { sort(point+i,point+tot,cmp); int np=point[i]; if(du[np]>0)return -1; if(du[np]==du[point[i+1]]&&i+1<tot)anss=0; ans[i]=np; for(int j=0;j<ps[np].size();j++) du[ps[np][j]]--; } } int main() { freopen("t.txt","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(i==j)continue; if(a[i]==a[j]) { add(j*2,i*2-1); add(i*2,j*2-1); } if(i==b[j]) { add(i*2,j*2); add(j*2-1,i*2-1); } if(b[i]==b[j]) { add(i*2-1,j*2); add(j*2-1,i*2); } if((a[i]==c[j]&&i!=b[j])) { add(i*2,j*2); add(j*2-1,i*2-1); } } strongconnect(); for(int i=1;i<tot;i++) { memset(vis,0,sizeof(vis)); ps[i].clear(); for(int j=0;j<strong[i].size();j++) { int np=strong[i][j]; for(int k=0;k<po[np].size();k++) { int nc=color[po[np][k]]; if(nc==i)continue; if(vis[nc]){continue;} else{vis[nc]=true;ps[i].push_back(nc);du[nc]++;} } } } int ans[maxn*2]; topo(ans); int anss[maxn]; for(int i= tot-1;i>=1;i--) { int np=ans[i]; for(int i=0;i<strong[np].size();i++) { int npp=strong[np][i]; if(anss[(npp+1)/2]==0) anss[((npp+1)/2)]=(npp+1)%2+1; } } for(int i=1;i<n;i++) printf("%d ",anss[i]); printf("%d\n",anss[n]); return 0; }
Ural 1382 2SAT
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。