图老师设计创意栏目是一个分享最好最实用的教程的社区，我们拥有最用心的各种教程，今天就给大家分享弦图ZOJ 1015 Fishing Net 判定方法的教程，热爱PS的朋友们快点看过来吧！
【 tulaoshi.com - 编程语言 】
做题思路：
贴代码：(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; jlen; j++)//在此WA了一天有木有。。。
if(num[ temp[0] ]num[ temp[j] ])
swap(temp[0], temp[j]);
for(j=1; jlen; 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; im; 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;
}
来源:http://www.tulaoshi.com/n/20160219/1598860.html
看过《弦图ZOJ 1015 Fishing Net 判定方法》的人还看了以下文章 更多>>
