String graph ZOJ 1015 Fishing Net determination method

  • 2020-04-01 21:25:10
  • OfStack

Train of thought to solve the problem. :
1 string diagram, looked a weekend to have no! Too weak, the algorithm is exactly in accordance with the CDQ PPT on the maximum potential algorithm (MCS) to find the perfect elimination sequence. Sumbit 19 times, providing a lot of denominators for WA... Write more to backup yourself.
Useful information:  
Theorem 3: a graph is a string graph if and only if it has a perfect elimination sequence. So get the perfect elimination sequence first:

< img SRC = "/ / files.jb51.net/file_images/article/201211/2012111414512650.jpg" border = 0 small = "0" >


4. How to determine whether the perfect elimination sequence is obtained:

< img SRC = "/ / files.jb51.net/file_images/article/201211/2012111414512651.jpg" border = 0 small = "0" >
Code paste :(complexity of 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++)//Have you been here for a day?
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("Perfectn"); 
else 
puts("Imperfectn"); 
} 
return 0; 
} 


Related articles: