bbsvs

弦图ZOJ 1015 Fishing Net 判定用法

作者:bbsvs 时间:2017-08-04

这篇文章主要是详细介绍弦图ZOJ 1015 Fishing Net 判定用法

1 弦图,看了一个周末有木有!太弱了点,算法完全按照CDQ的PPT上给的最大势算法(MCS)求完美消除序列。前前后后sumbit了19次,为WA提供了大量分母啊。。。。 多写点为自己备份吧。 

2 有用的资料: 

3 定理:一个图是弦图当且仅当它有一个完美消除序列。所以要先搞到完美消除序列: 

10.jpg

4 如何判断搞到的是不是完美消除序列: 

11.jpg


贴代码:(V*V的复杂度。。。) 

#include <iostream> 
#include <cstdio> 
#include <cstring> 
#include <algorithm> 
using namespace std; 
const int maxn=1000+10; 
int gra[maxn][maxn]; 
int n, m; 
int label[maxn], temp[maxn], num[maxn]; 
void numberVertex() 
{ 
int i, j; 
//label[n]=0, num[n]=1; 
for(i=n; i>=1; i--) 
{ 
int mm=-1, pos; 
for(j=1; j<=n; j++) 
{ 
if( !num[j] && label[j]>mm) 
{ 
mm=label[j]; 
pos=j; 
} 
} 
num[pos]=i; 
for(j=1; j<=n; j++) 
{ 
if( !num[j] && ( gra[pos][j] || gra[j][pos] ) ) 
label[j]++; 
} 
} 
return ; 
} 
int check() 
{ 
int i, j, flag=1; 
for(i=1; i<=n && flag; i++) 
{ 
memset(temp,0,sizeof(temp)); 
int len=0; 
for(j=1; j<=n; j++) 
{ 
if( num[i]<num[j] && gra[ i ][ j ] ) 
{ 
temp[len++]=j; 
} 
} 
for(j=1; j<len; j++)//在此WA了一天有木有。。。 
if(num[ temp[0] ]>num[ temp[j] ]) 
swap(temp[0], temp[j]); 
for(j=1; j<len; j++) 
if( !gra[ temp[0] ][ temp[j] ] ) 
{ 
flag=0; 
break; 
} 
} 
return flag; 
} 
int main() 
{ 
while( scanf("%d %d",&n,&m)!=EOF ) 
{ 
if(n==0 && m==0) 
break; 
memset(label,0,sizeof(label)); 
memset(num,0,sizeof(num)); 
memset(gra,0,sizeof(gra)); 
for(int i=0; i<m; i++) 
{ 
int x, y; 
scanf("%d %d",&x, &y); 
gra[x][y]=gra[y][x]=1; 
} 
numberVertex(); 
if( check() ) 
puts("Perfect\n"); 
else 
puts("Imperfect\n"); 
} 
return 0; 
}


TAG:
swap   fishing