洛谷P3209 [HNOI2010]PLANAR

首先用一波神奇的操作，平面图边数m<=3*n-6，直接把m降到n，

然后对于冲突的边一条环内，一条环外，可以用并查集或者2Sat做，

当然并查集是无向的，2Sat是有向的，显然用并查集比较好复杂度大概是O(T*n*n)

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #include<cstring>

 #define pb push_back

 #define pii pair<int,int>

 #define ft first

 #define sc second

 #define MAXN 200000+10

 using namespace std;

 int n,m;

 int b[MAXN],d[MAXN],f[MAXN];

 pii E[MAXN];

 int find(int x){return (f[x]==x?x:f[x]=find(f[x]));}

 void init_find(){

     for(int i=;i<=(m<<);i++)f[i]=i;

 }

 void lik(int x,int y){

     x=find(x),y=find(y);

     if(x!=y)f[x]=y;

 }

 int solve(){

     scanf("%d%d",&n,&m);

     init_find();

     for(int i=;i<=m;i++)scanf("%d%d",&E[i].ft,&E[i].sc);

     int t;

     for(int i=;i<=n;i++)scanf("%d",&t),d[t]=i;

     if(m>*n-)return ;

     memset(b,,sizeof(b));

     for(int i=;i<=m;i++){

         E[i].ft=d[E[i].ft],E[i].sc=d[E[i].sc];

         if(E[i].ft>E[i].sc){swap(E[i].ft,E[i].sc);}

         if(E[i].sc-E[i].ft==||E[i].sc-E[i].ft==n-)b[i]=;

     }

     pii x,y;

     for(int i=;i<=m;i++){

         if(b[i])continue;

         for(int j=i+;j<=m;j++){

             if(b[j])continue;

             x=E[i],y=E[j];

             if(x.ft==y.ft||x.ft==y.sc)continue;

             if(x.sc==y.ft||x.sc==y.sc)continue;

             if(x.ft==x.sc||y.ft==y.sc)continue;

             if(x.ft>y.ft)swap(x,y);

             if(y.ft<x.sc&&x.sc<y.sc){

                 if(find(i)==find(j))return ;

                 lik(i,j+m),lik(j,i+m);

             }

         }

     }

     return ;

 }

 int main()

 {

 //    freopen("data.in","r",stdin);

     int T;

     scanf("%d",&T);

     while(T--){

         if(solve())printf("YES\n");

         else printf("NO\n");

     }

     return ;

 }

并查集

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #include<cstring>

 #define pb push_back

 #define pii pair<int,int>

 #define ft first

 #define sc second

 #define MAXN 200000+10

 using namespace std;

 struct TSat{

     int n;

     int fst[MAXN],nxt[MAXN],to[MAXN];

     int cnt;

     void add(int x,int y){

         nxt[++cnt]=fst[x],fst[x]=cnt,to[cnt]=y;

     }

     void ins(int x,int y){

         add(x,y+n);

         add(x+n,y);

     }

     int dfn[MAXN],low[MAXN];

     int cmp[MAXN],sta[MAXN],vis[MAXN],top;

     int time_dex,tmp;

     void init(int n){

         this->n=n;

         time_dex=tmp=cnt=top=;

         memset(dfn,,sizeof(dfn));

         memset(low,,sizeof(low));

         memset(vis,,sizeof(vis));

         memset(fst,,sizeof(fst));

         memset(nxt,,sizeof(nxt));

         memset(to,,sizeof(to));

         memset(cmp,,sizeof(cmp));

     }

     void Tarjan(int x){

         dfn[x]=low[x]=++time_dex;

         sta[++top]=x;

         vis[x]=;

         for(int e=fst[x];e;e=nxt[e]){

             int &y=to[e];

             if(!dfn[y]){

                 Tarjan(y);

                 low[x]=min(low[x],low[y]);

             }

             else if(vis[y]){

                 low[x]=min(low[x],dfn[y]);

             }

         }

         if(low[x]==dfn[x]){

             tmp++;

             while(sta[top+]!=x){

                 cmp[sta[top]]=tmp;

                 vis[sta[top]]=;

                 top--;

             }

         }

     }

     bool check(){

         for(int i=;i<=(n<<);i++){

             if(!dfn[i])Tarjan(i);

         }

         for(int i=;i<=n;i++){

             if(cmp[i]==cmp[i+n])

                 return ;

         }

         return ;

     }

 }TS;

 int n,m;

 int b[MAXN],d[MAXN];

 pii E[MAXN];

 int solve(){

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++)scanf("%d%d",&E[i].ft,&E[i].sc);

     int t;

     for(int i=;i<=n;i++)scanf("%d",&t),d[t]=i;

     if(m>*n-)return ;

     TS.init(m);

     memset(b,,sizeof(b));

     for(int i=;i<=m;i++){

         E[i].ft=d[E[i].ft],E[i].sc=d[E[i].sc];

         if(E[i].ft>E[i].sc){swap(E[i].ft,E[i].sc);}

         if(E[i].sc-E[i].ft==||E[i].sc-E[i].ft==n-)b[i]=;

     }

     pii x,y;

     for(int i=;i<=m;i++){

         if(b[i])continue;

         for(int j=i+;j<=m;j++){

             if(b[j])continue;

             x=E[i],y=E[j];

             if(x.ft==y.ft||x.ft==y.sc)continue;

             if(x.sc==y.ft||x.sc==y.sc)continue;

             if(x.ft==x.sc||y.ft==y.sc)continue;

             if(x.ft>y.ft)swap(x,y);

             if(y.ft<x.sc&&x.sc<y.sc){

                 TS.ins(i,j);

                 TS.ins(j,i);

             }

         }

     }

     return TS.check();

 }

 int main()

 {

 //    freopen("data.in","r",stdin);

     int T;

     scanf("%d",&T);

     while(T--){

         if(solve())printf("YES\n");

         else printf("NO\n");

     }

     return ;

 }

2Sat

巴特西

洛谷P3209 [HNOI2010]PLANAR

最新文章

热门文章