[關鍵字]：圖論 二分圖

[題目大意]：給出一個帶有漢密爾頓回路的圖，判斷它是否是一個平面圖。

//==============================================================================

[分析]：漢密爾頓回路回練成一個環，這個圖必定被分成兩部分，如果兩條邊相交無論同時在內還是在外都會相交，只有一條在環內一條在外才行——二分圖！首先判斷出那些邊不再回路上然后把有矛盾的邊連邊利用染色法判斷能否構成二分圖，二分圖的成立決定了平面圖的成立。還有一點，平面圖內設點數為v邊數為e面數為r，v-e+r=2 e<=3*v-6?r<=2*v-4。

[代碼]：

View Code #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

const int MAXE=10010;
const int MAXV=300;

struct node
{
int x,y;
}e2[MAXE];
int test,n,m,sum;
int h[MAXV],rank[MAXV],c[MAXV];
bool map[MAXV][MAXV],flag;
vector<int> e[MAXE],dag[MAXE];
vector<int>::iterator it;

bool Fright(int x1,int y1,int x2,int y2)
{
if (x1==x2 || x1==y2 || y1==x2 || y1==y2) return 0;
x1=rank[x1],y1=rank[y1];
x2=rank[x2],y2=rank[y2];
if (x1>y1) swap(x1,y1);
return (x1<x2 && x2<y1)!=(x1<y2 && y2<y1);
}

void Colour(int v,int x)
{
// printf("%d\n",v);
c[v]=x;
int size=dag[v].size();
for (int i=0;i<size;++i)
{
//printf("%d %d\n",v,dag[v][i]);
if (!c[dag[v][i]]) Colour(dag[v][i],-x); else
if (c[dag[v][i]]==x) flag=0;
if (!flag) return;
}
}

int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%d",&test);
while (test--)
{
scanf("%d%d",&n,&m);
flag=1;
for (int i=1;i<=n;++i) e[i].clear();
for (int i=1;i<=m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
e[x].push_back(y);
}
for (int i=1;i<=n;++i)
scanf("%d",&h[i]),rank[h[i]]=i;
memset(map,0,sizeof(map));
for (int i=2;i<=n;++i)
map[h[i-1]][h[i]]=map[h[i]][h[i-1]]=1;
map[h[n]][h[1]]=map[h[1]][h[n]]=1;
if (m>n*3-6)
{
printf("NO\n");
continue;
}
sum=0;
for (int i=1;i<=n;++i)
for (it=e[i].begin();it<e[i].end();++it)
if (!map[i][*it]) e2[++sum].x=i,e2[sum].y=*it;
//printf("%d\n",sum);
//for (int i=1;i<=sum;++i)
//printf("%d %d\n",e2[i].x,e2[i].y);
for (int i=1;i<=sum;++i) dag[i].clear();
for (int i=1;i<=sum;++i)
for (int j=i+1;j<=sum;++j)
if (Fright(e2[i].x,e2[i].y,e2[j].x,e2[j].y)) dag[i].push_back(j),dag[j].push_back(i);
//for (int i=1;i<=sum;++i)
//for (it=dag[i].begin();it<dag[i].end();++it)
//printf("%d %d\n",i,*it);
//printf("//=============================\n");
memset(c,0,sizeof(c));
for (int i=1;i<=sum;++i)
if (!c[i])
{
Colour(i,1);
//printf("//================================\n");
if (!flag) break;
}
if (flag) printf("YES\n"); else printf("NO\n");
}
return 0;
}

轉載于:https://www.cnblogs.com/procedure2012/archive/2012/04/07/2435997.html

總結

以上是生活随笔為你收集整理的[HNOI2010 Planar平面图判定]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。