[2-SAT][POJ2683][HDU1814]2-SAT两种模板

2019-11-11 02:17:03

字体：大中小

来源：转载

供稿：网友

2-SAT有两种模板，一种O(M) $O(M)$ 可以求任意可行解，另一种O(MN) $O(MN)$ 十分暴力，所以可以求字典序最小或最大解

POJ2683

给定限制求任意可行解

这题就是O(M) $O(M)$ 的模板。

#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>#include <string>#include <queue>#define N 4010#define mp(a,b) make_pair(a,b)using namespace std;typedef pair<int,int> PRs;typedef pair<prs,prs> prs4;prs4 p[N];int n,cnt,tp,ti,g;int G[N],sta[N],dfn[N],low[N],vis[N],bel[N],nG[N],v[N],d[N],opp[N];struct edge{ int t,nx;}E[N*N<<1];queue<int> Q;inline bool cover(prs a,prs b){ if(a.first>b.first) swap(a,b); return a.second>b.first;}inline void InserT(int x,int y){ E[++cnt].t=x;E[cnt].nx=G[y];G[y]=cnt;}inline void Insert(int x,int y){ E[++cnt].t=y;E[cnt].nx=nG[x];nG[x]=cnt;d[y]++;}void tarjan(int x){ vis[x]=1; dfn[x]=low[x]=++ti; sta[++tp]=x; for(int i=G[x];i;i=E[i].nx){ if(!vis[E[i].t]) tarjan(E[i].t); if(vis[E[i].t]==1) low[x]=min(low[x],low[E[i].t]); } if(low[x]==dfn[x]){ ++g; int k; do{ k=sta[tp--]; bel[k]=g; vis[k]=2; }while(tp&&k!=x); }}int main(){ freopen("t.in","r",stdin); freopen("t.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++){ int s,s1,t,t1,l; scanf("%d:%d %d:%d %d",&s,&s1,&t,&t1,&l); s=s*60+s1; t=t*60+t1; p[i]=mp(mp(s,s+l),mp(t-l,t)); } for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){ if(cover(p[i].first,p[j].first)) InserT(i<<1,j<<1|1),InserT(j<<1,i<<1|1); if(cover(p[i].first,p[j].second)) InserT(i<<1,j<<1),InserT(j<<1|1,i<<1|1); if(cover(p[i].second,p[j].first)) InserT(i<<1|1,j<<1|1),InserT(j<<1,i<<1); if(cover(p[i].second,p[j].second)) InserT(i<<1|1,j<<1),InserT(j<<1|1,i<<1); } for(int i=2;i<=(n<<1|1);i++) if(!dfn[i]) tarjan(i); for(int i=1;i<=n;i++) if(bel[i<<1]==bel[i<<1|1]) {puts("NO");return 0;} for(int k=2;k<=(n<<1|1);k++){ for(int i=G[k];i;i=E[i].nx) if(bel[E[i].t]!=bel[k]) Insert(bel[E[i].t],bel[k]); opp[bel[k]]=bel[k^1]; } memset(vis,0,sizeof(vis)); for(int i=1;i<=g;i++) if(!d[i]) Q.push(i); while(!Q.empty()){ int x=Q.front(); Q.pop(); if(!vis[x]) vis[x]=1,vis[opp[x]]=2; for(int i=nG[x];i;i=E[i].nx) if(!(--d[E[i].t])) Q.push(E[i].t); } puts("YES"); for(int i=1;i<=n;i++){ int s,s1,t,t1; if(vis[bel[i<<1|1]]==1){ s=p[i].first.first/60,s1=p[i].first.first%60; t=p[i].first.second/60,t1=p[i].first.second%60; printf("%02d:%02d %02d:%02d/n",s,s1,t,t1); } else{ s=p[i].second.first/60,s1=p[i].second.first%60; t=p[i].second.second/60,t1=p[i].second.second%60; printf("%02d:%02d %02d:%02d/n",s,s1,t,t1); } }}

HDU 2683

给定限制，求字典序最小解

O(NM) $O(NM)$ 模板

#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>#include <string>#include <queue>#define N 4010#define mp(a,b) make_pair(a,b)using namespace std;typedef pair<int,int> prs;typedef pair<prs,prs> prs4;prs4 p[N];int n,cnt,tp,ti,g;int G[N],sta[N],dfn[N],low[N],vis[N],bel[N],nG[N],v[N],d[N],opp[N];struct edge{ int t,nx;}E[N*N<<1];queue<int> Q;inline bool cover(prs a,prs b){ if(a.first>b.first) swap(a,b); return a.second>b.first;}inline void InserT(int x,int y){ E[++cnt].t=x;E[cnt].nx=G[y];G[y]=cnt;}inline void Insert(int x,int y){ E[++cnt].t=y;E[cnt].nx=nG[x];nG[x]=cnt;d[y]++;}void tarjan(int x){ vis[x]=1; dfn[x]=low[x]=++ti; sta[++tp]=x; for(int i=G[x];i;i=E[i].nx){ if(!vis[E[i].t]) tarjan(E[i].t); if(vis[E[i].t]==1) low[x]=min(low[x],low[E[i].t]); } if(low[x]==dfn[x]){ ++g; int k; do{ k=sta[tp--]; bel[k]=g; vis[k]=2; }while(tp&&k!=x); }}int main(){ freopen("t.in","r",stdin); freopen("t.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++){ int s,s1,t,t1,l; scanf("%d:%d %d:%d %d",&s,&s1,&t,&t1,&l); s=s*60+s1; t=t*60+t1; p[i]=mp(mp(s,s+l),mp(t-l,t)); } for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){ if(cover(p[i].first,p[j].first)) InserT(i<<1,j<<1|1),InserT(j<<1,i<<1|1); if(cover(p[i].first,p[j].second)) InserT(i<<1,j<<1),InserT(j<<1|1,i<<1|1); if(cover(p[i].second,p[j].first)) InserT(i<<1|1,j<<1|1),InserT(j<<1,i<<1); if(cover(p[i].second,p[j].second)) InserT(i<<1|1,j<<1),InserT(j<<1|1,i<<1); } for(int i=2;i<=(n<<1|1);i++) if(!dfn[i]) tarjan(i); for(int i=1;i<=n;i++) if(bel[i<<1]==bel[i<<1|1]) {puts("NO");return 0;} for(int k=2;k<=(n<<1|1);k++){ for(int i=G[k];i;i=E[i].nx) if(bel[E[i].t]!=bel[k]) Insert(bel[E[i].t],bel[k]); opp[bel[k]]=bel[k^1]; } memset(vis,0,sizeof(vis)); for(int i=1;i<=g;i++) if(!d[i]) Q.push(i); while(!Q.empty()){ int x=Q.front(); Q.pop(); if(!vis[x]) vis[x]=1,vis[opp[x]]=2; for(int i=nG[x];i;i=E[i].nx) if(!(--d[E[i].t])) Q.push(E[i].t); } puts("YES"); for(int i=1;i<=n;i++){ int s,s1,t,t1; if(vis[bel[i<<1|1]]==1){ s=p[i].first.first/60,s1=p[i].first.first%60; t=p[i].first.second/60,t1=p[i].first.second%60; printf("%02d:%02d %02d:%02d/n",s,s1,t,t1); } else{ s=p[i].second.first/60,s1=p[i].second.first%60; t=p[i].second.second/60,t1=p[i].second.second%60; printf("%02d:%02d %02d:%02d/n",s,s1,t,t1); } }}

表示本蒟蒻只会打模板，之前还把2-SAT搞成2-SET…… 之后还得学各种2-SAT乱搞

上一篇：51nod 1134 最长递增子序列 dp(经典)

下一篇：例题：统计字母个数