1 弦图，看了一个周末有木有！太弱了点，算法完全按照CDQ的PPT上给的最大势算法（MCS）求完美消除序列。前前后后sumbit了19次，为WA提供了大量分母啊。。。。 多写点为自己备份吧。
2 有用的资料：
3 定理：一个图是弦图当且仅当它有一个完美消除序列。所以要先搞到完美消除序列：
4 如何判断搞到的是不是完美消除序列：
贴代码：(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;
}
以上就是【弦图ZOJ 1015 Fishing Net 判定方法】的全部内容了,欢迎留言评论进行交流!