弦图ZOJ 1015 Fishing Net 判定方法
来源：爱站网时间：2019-09-16编辑：网友分享
在C语言的开发的过程中，总是有需要判定的东西，今天这篇文章是爱站技术频道小编为大家带来的弦图ZOJ 1015 Fishing Net 判定方法，一起跟着爱站技术频道小编的步伐来了解一下。
在C语言的开发的过程中，总是有需要判定的东西，今天这篇文章是爱站技术频道小编为大家带来的弦图ZOJ 1015 Fishing Net 判定方法，一起跟着爱站技术频道小编的步伐来了解一下。
做题思路：
1 弦图，看了一个周末有木有！太弱了点，算法完全按照CDQ的PPT上给的最大势算法（MCS）求完美消除序列。前前后后sumbit了19次，为WA提供了大量分母啊。。。。 多写点为自己备份吧。
2 有用的资料：
3 定理：一个图是弦图当且仅当它有一个完美消除序列。所以要先搞到完美消除序列：
4 如何判断搞到的是不是完美消除序列：
贴代码：(V*V的复杂度。。。)
#include
#include
#include
#include
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 {
if( !num[j] && label[j]>mm)
{
mm=label[j];
pos=j;
}
}
num[pos]=i;
for(j=1; j {
if( !num[j] && ( gra[pos][j] || gra[j][pos] ) )
label[j]++;
}
}
return ;
}
int check()
{
int i, j, flag=1;
for(i=1; i {
memset(temp,0,sizeof(temp));
int len=0;
for(j=1; j {
if( num[i]
temp[len++]=j;
}
}
for(j=1; j
swap(temp[0], temp[j]);
for(j=1; 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
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 判定方法，希望对你学习这方面知识有帮助，感谢大家继续支持爱站技术频道！
上一篇：解析C++实现迷宫算法实例
