P3209 [HNOI2010]平面图判定

题目：

若能将无向图 $G=(V, E)$ 画在平面上使得任意两条无重合顶点的边不相交，则称 $G$ 是平面图。判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要判定的是一类特殊的图，图中存在一个包含所有顶点的环，即存在哈密顿回路。

思路：

1.2-sat

关于平面图有一个性质，边数一定小于等于 $3n-6$ 。所以我们对于边数大的直接得到答案。其余的我们 $O(n^{2})$ 判断两条连边是否矛盾，把每条边分离成两个点表示边连在外部还是内部。如果矛盾就连边。

2.并查集

在一样的性质下，与 $i+n$ 相连的点表示不能与 $i$ 在同一侧，所以对于每对矛盾的边 $fa[getfa(x)]=getfa(y+n),fa[getfa(y)]=getfa(x+n)$ 。

如果如果有一对矛盾的点属于同一个集合，则不合法。

代码：

我写的是第二种啊，感觉代码比较短...

#include
      
       #define il inline#define _(d) while(d(isdigit(ch=getchar())))using namespace std;const int N=1e4+5,M=1e4+5;int n,m,v[N],l[N],tot,id[N],fa[N];struct node{    int x,y;}t[M];il int read(){   int x,f=1;char ch;   _(!)ch=='-'?f=-1:f;x=ch^48;   _()x=(x<<1)+(x<<3)+(ch^48);   return f*x;}il int getfa(int x){    if(fa[x]==x)return x;return fa[x]=getfa(fa[x]);}il bool cross(int u1,int v1,int u2,int v2){    u1=id[u1];v1=id[v1];u2=id[u2];v2=id[v2];    if(u1>v1)swap(u1,v1);if(u2>v2)swap(u2,v2);    return ((u1
       
        
         
          
           
            
             3*n-6){puts("NO");continue;} for(int i=2;i<=n;i++)l[v[i]]=v[i-1];l[v[1]]=v[n]; tot=0; for(int i=1;i<=m;i++) if(l[t[i].x]!=t[i].y&&l[t[i].y]!=t[i].x)t[++tot]=t[i]; m=tot; for(int i=1;i<=(m<<1);i++)fa[i]=i;bool pd=0; for(int i=1;i<=m;i++)for(int j=i+1;j<=m;j++){ if(!cross(t[i].x,t[i].y,t[j].x,t[j].y))continue; int x=getfa(i),y=getfa(j); if(x==y){pd=1;break;} fa[x]=getfa(j+m);fa[y]=getfa(i+m); } if(pd)puts("NO");else puts("YES"); } return 0;}
            
           
          
         
        
       
      

 

dtoj#3858. 游戏

题目：

小 L 计划进行 $ n $ 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。小 L 的赛车有三辆，分别用大写字母A、B、C表示。

地图一共有四种，分别用小写字母x、a、b、c表示。

其中，赛车A不适合在地图a上使用，赛车B不适合在地图b上使用，赛车C不适合在地图c上使用，而地图x则适合所有赛车参加。

适合所有赛车参加的地图并不多见，最多只会有 $ d $ 张。

$ n $ 场游戏的地图可以用一个小写字母组成的字符串描述。例如： $ S=xaabxcbc $ 表示小L计划进行 $ 8 $ 场游戏，其中第 $ 1 $ 场和第 $ 5 $ 场的地图类型是x，适合所有赛车，第2场和第3场的地图是a，不适合赛车A，第4场和第7场的地图是b，不适合赛车B，第6场和第8场的地图是c，不适合赛车C。

小 L 对游戏有一些特殊的要求，这些要求可以用四元组 $ (i,h_i,j,h_j) $ 来描述，表示若在第 $ i $ 场使用型号为 $ h_i $ 的车子，则第 $ j $ 场游戏要使用型号为 $ h_j $ 的车子。

你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。

如果无解，输出 $ -1 $ 。

 思路：

当 $d=0$ 时对于每场比赛有两种选择，于是想到 $2-sat$ 。

考虑对于限制

如果 $i$ 场比赛不能放 $h_{i}$ ，那就忽略这个限制。

如果第 $j$ 场不能放 $h_{j}$ ，那就意味着不能在 $i$ 场放 $h_{i}$ 那就连接 $(放 $h_{i}$,不放 $h_{i}$ )。

其他情况就是连接 (放 $h_{i}$ ,放 $h_{j}$ )，（不放 $h_{j}$ ,不放 $h_{i}$ ）。

代码：

#include
      
       #define il inline#define _(d) while(d(isdigit(ch=getchar())))using namespace std;const int N=1e5+5;char s[N];bool vis[N];int sta[N],top,tot,col[N],c;int n,d,m,pos[N],cnt,head[N],ne[N<<1],to[N<<1],dfn[N],low[N];struct node{    int x,y;char hx,hy;}t[N];il int read(){   int x,f=1;char ch;   _(!)ch=='-'?f=-1:f;x=ch^48;   _()x=(x<<1)+(x<<3)+(ch^48);   return f*x;}il char getc(){    char ch='0';    while(ch!='A'&&ch!='B'&&ch!='C')ch=getchar();    return ch;}il void ins(int x,int y){    ne[++cnt]=head[x];head[x]=cnt;to[cnt]=y;}il int id(int x,char ch,int op){    if(op==1){        if(s[x]=='a'){            if(ch=='B')return x;return x+n;        }        if(s[x]=='b'){            if(ch=='A')return x;return x+n;        }        if(s[x]=='c'){            if(ch=='A')return x;return x+n;        }    }    else{        if(s[x]=='a'){            if(ch=='B')return x+n;return x;        }        if(s[x]=='b'){            if(ch=='A')return x+n;return x;        }        if(s[x]=='c'){            if(ch=='A')return x+n;return x;        }    }}il void prin(int p,int op){//    printf("!!%d %d \n",b)    if(s[p]=='a'){        if(op==0)printf("B");else printf("C");    }    if(s[p]=='b'){        if(op==0)printf("A");else printf("C");    }    if(s[p]=='c'){        if(op==0)printf("A");else printf("B");    }}il void tarjan(int x){    dfn[x]=low[x]=++tot;sta[++top]=x;vis[x]=1;    for(int i=head[x];i;i=ne[i]){        if(!dfn[to[i]])tarjan(to[i]),low[x]=min(low[x],low[to[i]]);        else if(vis[to[i]])low[x]=min(low[x],dfn[to[i]]);    }    if(dfn[x]==low[x]){        vis[x]=0;col[x]=++c;        while(sta[top]!=x)vis[sta[top]]=0,col[sta[top--]]=c;        top--;    }}il bool pd(){    cnt=0;    for(int i=1;i<=(n<<1);i++)head[i]=dfn[i]=0;cnt=c=tot=0;    for(int i=1;i<=m;i++){        if(t[i].hx+32==s[t[i].x])continue;        if(t[i].hy+32==s[t[i].y]){            ins(id(t[i].x,t[i].hx,1),id(t[i].x,t[i].hx,0));            continue;        }        ins(id(t[i].x,t[i].hx,1),id(t[i].y,t[i].hy,1));        ins(id(t[i].y,t[i].hy,0),id(t[i].x,t[i].hx,0));    }    for(int i=1;i<=(n<<1);i++)if(!dfn[i])tarjan(i);    for(int i=1;i<=n;i++)if(col[i]==col[i+n])return 0;    for(int i=1;i<=n;i++){        if(col[i]
       
        d){        if(pd())exit(0);        return;    }    s[pos[x]]='a';dfs(x+1);    s[pos[x]]='b';dfs(x+1);}int main(){    n=read();read();    scanf(" %s",s+1);    for(int i=1;i<=n;i++)if(s[i]=='x')pos[++d]=i;    m=read();    for(int i=1;i<=m;i++){        t[i].x=read();t[i].hx=getc();        t[i].y=read();t[i].hy=getc();    }    dfs(1);puts("-1");    return 0;}
       
      

 

bzoj3495 PA2010 Riddle

题目：

有 $n$ 个城镇被分成了 $k$ 个郡，有 $m$ 条连接城镇的无向边。

要求给每个郡选择一个城镇作为首都，满足每条边至少有一个端点是首都。

思路：

有一个前缀建图的思路，对于每一个城镇去一个前缀和，因为一个城镇只能有一个首都，所以前缀和取值为 $0/1$ 。

于是有以下几种关系(前为条件后为结果)：

1. $a[i]=1,s[i]=1$ 

2. $s[i]=0,a[i]=1$ 

3. $a[i]=1,s[i-1]=0$ 

4. $s[i-1]=1,a[i]=0$ 

5. $s[i-1]=1,s[i]=1$

6. $s[i]=0,s[i-1]=0$

代码：

#include
       
        #define il inline#define _(d) while(d(isdigit(ch=getchar())))using namespace std;const int N=4e6+5;bool vis[N];int col[N],sta[N],top,c;int n,m,k,head[N],ne[N<<1],to[N<<1],cnt,dfn[N],low[N],tot;il int read(){   int x,f=1;char ch;   _(!)ch=='-'?f=-1:f;x=ch^48;   _()x=(x<<1)+(x<<3)+(ch^48);   return f*x;}il void ins(int x,int y){    ne[++cnt]=head[x];head[x]=cnt;to[cnt]=y;}il void tarjan(int x){    dfn[x]=low[x]=++tot;sta[++top]=x;vis[x]=1;    for(int i=head[x];i;i=ne[i]){        if(!dfn[to[i]])tarjan(to[i]),low[x]=min(low[x],low[to[i]]);        else if(vis[to[i]])low[x]=min(low[x],dfn[to[i]]);    }    if(dfn[x]==low[x]){        vis[x]=0;col[x]=++c;        while(sta[top]!=x)vis[sta[top]]=0,col[sta[top--]]=c;        top--;    }}il bool pd(){    for(int i=1;i<=n;i++)if(col[i]==col[i+n])return 0;    for(int i=n*2+1;i<=n*3;i++)if(col[i]==col[i+n])return 0;    return 1;}int main(){    n=read();m=read();k=read();    for(int i=1;i<=m;i++){        int x=read(),y=read();        ins(x+n,y);ins(y+n,x);    }    for(int i=1;i<=n;i++)ins(i,i+n*2),ins(i+n*3,i+n);    for(int i=1;i<=k;i++){        int d=read(),las=read();        for(int j=2;j<=d;j++){            int now=read();            ins(now,las+n*3);ins(las+n*2,now+n);            ins(las+n*2,now+n*2);ins(now+n*3,las+n*3);las=now;        }    }    for(int i=1;i<=(n<<2);i++)if(!dfn[i])tarjan(i);    if(pd())puts("TAK");else puts("NIE");    return 0;}