首页 > 代码库 > UVALive 4849 String Phone（2-sat、01染色）
UVALive 4849 String Phone（2-sat、01染色）
题目一眼看去以为是4-sat。。。
题意：给n（n<=3000）个黑方块的坐标，保证黑方块没有公共边。对于每个黑方块选一个角作为结点，使得所选结点满足输入的一个无向图。其中距离为曼哈顿距离。输出是否有解。possible或impossible。
对于每个黑方块，4个角落必须选且仅选一个。一开始2-sat建模是对于一个pnt[i]，有4对点pnt[i][0], pnt[i][0]‘, pnt[i][1], pnt[i][1]‘, pnt[i][2], pnt[i][2]‘, pnt[i][3], pnt[i][3]‘。但是这样建模只能保证4个角落至多选一个（pnt[i][j]连pnt[i][k]‘ (k!=j)），保证不了至少选一个。
参考别人代码，发现神做法。类似2-sat的嵌套。。。01染色+2sat
把4个角落分组，左上和右下为第0组，右上和左下为第1组。（因为左上和右下的曼哈顿距离为2，有可能共存；右上和左下同理）。而左上和右上不可能共存，左上和左下同理。（没必要也没有意义把不共存的分为一组。）
通过染色，可以确定每个黑方块只有2种选择（黑方块染为第0组，则只能选左上或右下，且必须选且仅选一个；第1组同理）。到这里就可以看得出，显然的2-sat模型。感觉就像是2*2sat==4sat。
#pragma comment (linker,"/STACK:102400000,102400000")#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <vector>#include <algorithm>#include <cmath>#include <queue>#include <set>#include <map>#include <stack>using namespace std;#define eps 1e-8#define ll long long#define mxn 2600#define mxe 26000#define inf 0x3f3f3f3f#define MP make_pair#define maxn 6060#define maxm 310000*8struct Edge{ int v,w,nxt;}e[maxm];int head[maxn],esz;void init(){esz=0;memset(head,-1,sizeof(head));}void addedge(int u,int v,int w){ e[esz].v=v,e[esz].w=w,e[esz].nxt=head[u]; head[u]=esz++;}struct SAT{ Edge e[maxm]; int head[maxn], em; void init(){em=0;memset(head,-1,sizeof(head));} void add(int u,int v){ e[esz].v=v,e[esz].nxt=head[u]; head[u]=esz++; } int dfn[maxn],low[maxn],id,cnt; bool ins[maxn]; int st[maxn],top; int belong[maxn]; void strong(int x,int fa){ dfn[x]=low[x]=++id; st[top++]=x; ins[x]=true; for(int i=head[x];i!=-1;i=e[i].nxt){ int v = e[i].v; if(!dfn[v]){ strong(v,x); low[x] = min(low[x],low[v]); }else if(ins[v]) low[x] = min(low[x], dfn[v]); } if(dfn[x]==low[x]){ int u=-1;++cnt; while(u!=x){ u = st[--top]; ins[u]=false; belong[u]=cnt; } } } bool tarjan(int n){ id=cnt=top=0; memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(ins,0,sizeof(ins)); for(int i=0;i<n;++i) if(!dfn[i]) strong(i,-1); for(int i=0;i<n;i+=2) if(belong[i]==belong[i^1]) return false; return true; }}sat;int dx[2][2]={{0,1},{0,1}};int dy[2][2]={{0,1},{1,0}};struct Pnt{ int x,y; Pnt(){} Pnt(int xx,int yy):x(xx),y(yy){}}pnt[maxn];Pnt pp[maxn][2];int dis(Pnt a,Pnt b){return abs(a.x-b.x)+abs(a.y-b.y);}int kind[maxn];bool color(int u,int sign){ kind[u] = sign; for(int i=head[u];i!=-1;i=e[i].nxt){ int v = e[i].v; int sign2 = (dis(pnt[u],pnt[v])&1)^(e[i].w&1)^sign; if(kind[v]==-1){ if(color(v,sign2)==false) return false; }else if(kind[v]!=sign2) return false; } return true;}bool jud(int u,int sign,int n){ memset(kind,-1,sizeof(kind)); if(color(u,sign)==false) return false; for(int i=1;i<=n;++i){ pp[i][0] = Pnt(pnt[i].x+dx[kind[i]][0], pnt[i].y+dy[kind[i]][0]); pp[i][1] = Pnt(pnt[i].x+dx[kind[i]][1], pnt[i].y+dy[kind[i]][1]); } sat.init(); for(int i=1;i<=n;++i){ if(kind[i]==-1) continue; for(int j=head[i];j!=-1;j=e[j].nxt){ int to = e[j].v; int w = e[j].w; int dis1 = dis(pp[i][0], pp[to][0]); int dis2 = dis(pp[i][0], pp[to][1]); if(dis1!=w || dis2!=w){ if(dis1!=w && dis2!=w){ sat.add(2*i-2,2*i-1); }else if(dis1==w){ sat.add(2*i-2,2*to-2); }else if(dis2==w){ sat.add(2*i-2,2*to-1); } } dis1 = dis(pp[i][1], pp[to][0]); dis2 = dis(pp[i][1], pp[to][1]); if(dis1!=w || dis2!=w){ if(dis1!=w && dis2!=w){ sat.add(2*i-1,2*i-2); }else if(dis1==w){ sat.add(2*i-1,2*to-2); }else if(dis2==w){ sat.add(2*i-1,2*to-1); } } } } bool ans = sat.tarjan(n*2); return ans;}int fa[maxn];int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}int main(){ int t,n,m; scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d%d",&pnt[i].x,&pnt[i].y); scanf("%d",&m); init(); for(int i=0;i<=n;++i) fa[i]=i; for(int i=0;i<m;++i){ int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); fa[find(u)] = find(v); } bool yes = true; for(int i=1;i<=n;++i){ if(i==fa[i]){ if(jud(i,0,n)==false && jud(i,1,n)==false){ yes = false; break; } } } if(yes) puts("possible"); else puts("impossible"); } return 0;}
UVALive 4849 String Phone（2-sat、01染色）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。