欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

弦圖ZOJ 1015 Fishing Net 判定方法

 更新時(shí)間：2012年11月14日 14:59:49   作者：  
弦圖，算法完全按照CDQ的PPT上給的最大勢(shì)算法（MCS）完美消除序列..需要的朋友可以參考下
做題思路：
1 弦圖，看了一個(gè)周末有木有！太弱了點(diǎn)，算法完全按照CDQ的PPT上給的最大勢(shì)算法（MCS）求完美消除序列。前前后后sumbit了19次，為WA提供了大量分母啊。。。。 多寫點(diǎn)為自己備份吧。
2 有用的資料： 
3 定理：一個(gè)圖是弦圖當(dāng)且僅當(dāng)它有一個(gè)完美消除序列。所以要先搞到完美消除序列：


4 如何判斷搞到的是不是完美消除序列：


貼代碼：(V*V的復(fù)雜度。。。)

復(fù)制代碼 代碼如下:

#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;
}

相關(guān)文章

最新評(píng)論