蘇州其然軟件開(kāi)發(fā)培訓(xùn)

Java工程師就業(yè)前景

Java工程師就業(yè)前景

[2-SAT][POJ2683][HDU1814]2-SAT兩種模板

>

2-SAT有兩種模板，一種O(M) $O(M)可以求任意可行解，另一種<nobr>O(MN)</nobr> <script type="math/tex" id="MathJax-Element-2">O(MN)十分暴力，所以可以求字典序**小或**大解 </h5> <hr /> <h4 id="poj2683"> POJ2683 </h4> <p> 給定限制求任意可行解 </p> <p> 這題就是<nobr>O(M)</nobr> <script type="math/tex" id="MathJax-Element-3">O(M)的模板。 </p> #include &lt;cstdio&gt; #include &lt;iostream&gt; #include &lt;algorithm&gt; #include &lt;cstring&gt; #include &lt;string&gt; #include &lt;queue&gt; #define N 4010 #define mp(a,b) make_pair(a,b) using namespace std; typedef pair&lt;int,int&gt; PR</a>s; typedef pair&lt;prs,prs&gt; 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&lt;&lt;1]; queue&lt;int&gt; Q; inline bool cover(prs a,prs b){ if(a.first&gt;b.first) swap(a,b); return a.second&gt;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&amp;&amp;k!=x); } } int main(){ freopen("t.in","r",stdin); freopen("t.out","w",stdout); scanf("%d",&amp;n); for(int i=1;i&lt;=n;i ){ int s,s1,t,t1,l; scanf("%d:%d %d:%d %d",&amp;s,&amp;s1,&amp;t,&amp;t1,&amp;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&lt;=n;i ) for(int j=i 1;j&lt;=n;j ){ if(cover(p[i].first,p[j].first)) InserT(i&lt;&lt;1,j&lt;&lt;1|1),InserT(j&lt;&lt;1,i&lt;&lt;1|1); if(cover(p[i].first,p[j].second)) InserT(i&lt;&lt;1,j&lt;&lt;1),InserT(j&lt;&lt;1|1,i&lt;&lt;1|1); if(cover(p[i].second,p[j].first)) InserT(i&lt;&lt;1|1,j&lt;&lt;1|1),InserT(j&lt;&lt;1,i&lt;&lt;1); if(cover(p[i].second,p[j].second)) InserT(i&lt;&lt;1|1,j&lt;&lt;1),InserT(j&lt;&lt;1|1,i&lt;&lt;1); } for(int i=2;i&lt;=(n&lt;&lt;1|1);i ) if(!dfn[i]) tarjan(i); for(int i=1;i&lt;=n;i ) if(bel[i&lt;&lt;1]==bel[i&lt;&lt;1|1]) {puts("");return 0;} for(int k=2;k&lt;=(n&lt;&lt;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&lt;=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&lt;=n;i ){ int s,s1,t,t1; if(vis[bel[i&lt;&lt;1|1]]==1){ s=p[i].first.first/60,s1=p[i].first.first`; t=p[i].first.second/60,t1=p[i].first.second`; printf("d:d d:d\n",s,s1,t,t1); } else{ s=p[i].second.first/60,s1=p[i].second.first`; t=p[i].second.second/60,t1=p[i].second.second`; printf("d:d d:d\n",s,s1,t,t1); } } } <hr /> <h4 id="hdu-2683"> HDU 2683 </h4> <p> 給定限制，求字典序**小解 </p> <p> <nobr>O(NM)</nobr> <script type="math/tex" id="MathJax-Element-4">O(NM)模板 </p> #include &lt;cstdio&gt; #include &lt;iostream&gt; #include &lt;algorithm&gt; #include &lt;cstring&gt; #include &lt;string&gt; #include &lt;queue&gt; #define N 4010 #define mp(a,b) make_pair(a,b) using namespace std; typedef pair&lt;int,int&gt; prs; typedef pair&lt;prs,prs&gt; 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&lt;&lt;1]; queue&lt;int&gt; Q; inline bool cover(prs a,prs b){ if(a.first&gt;b.first) swap(a,b); return a.second&gt;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&amp;&amp;k!=x); } } int main(){ freopen("t.in","r",stdin); freopen("t.out","w",stdout); scanf("%d",&amp;n); for(int i=1;i&lt;=n;i ){ int s,s1,t,t1,l; scanf("%d:%d %d:%d %d",&amp;s,&amp;s1,&amp;t,&amp;t1,&amp;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&lt;=n;i ) for(int j=i 1;j&lt;=n;j ){ if(cover(p[i].first,p[j].first)) InserT(i&lt;&lt;1,j&lt;&lt;1|1),InserT(j&lt;&lt;1,i&lt;&lt;1|1); if(cover(p[i].first,p[j].second)) InserT(i&lt;&lt;1,j&lt;&lt;1),InserT(j&lt;&lt;1|1,i&lt;&lt;1|1); if(cover(p[i].second,p[j].first)) InserT(i&lt;&lt;1|1,j&lt;&lt;1|1),InserT(j&lt;&lt;1,i&lt;&lt;1); if(cover(p[i].second,p[j].second)) InserT(i&lt;&lt;1|1,j&lt;&lt;1),InserT(j&lt;&lt;1|1,i&lt;&lt;1); } for(int i=2;i&lt;=(n&lt;&lt;1|1);i ) if(!dfn[i]) tarjan(i); for(int i=1;i&lt;=n;i ) if(bel[i&lt;&lt;1]==bel[i&lt;&lt;1|1]) {puts("");return 0;} for(int k=2;k&lt;=(n&lt;&lt;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&lt;=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&lt;=n;i ){ int s,s1,t,t1; if(vis[bel[i&lt;&lt;1|1]]==1){ s=p[i].first.first/60,s1=p[i].first.first`; t=p[i].first.second/60,t1=p[i].first.second`; printf("d:d d:d\n",s,s1,t,t1); } else{ s=p[i].second.first/60,s1=p[i].second.first`; t=p[i].second.second/60,t1=p[i].second.second`; printf("d:d d:d\n",s,s1,t,t1); } } } <p> 表示本蒟蒻只會(huì)打模板，之前還把2-SAT搞成2-SET…… 之后還得學(xué)各種2-SAT亂搞 </p> </p> <p> <b>相關(guān)推薦：</b> </p> <hr /> <p> <a href="http://m.k67r.cn/px189_jssz/" target="_blank">蘇州JAVA培訓(xùn)</a>&nbsp; &nbsp;<a href="http://m.k67r.cn/px189_jssz/" target="_blank">蘇州JAVA培訓(xùn)班</a>&nbsp; &nbsp;<a href="http://m.k67r.cn/px189_jssz/" target="_blank">蘇州JAVA培訓(xùn)機(jī)構(gòu)</a> </p>$