弦圖ZOJ 1015 Fishing Net 判定方法
更新時間：2012年11月14日 14:59:49 作者：
弦圖，算法完全按照CDQ的PPT上給的最大勢算法（MCS）完美消除序列..需要的朋友可以參考下
做題思路：
1 弦圖，看了一個周末有木有！太弱了點，算法完全按照CDQ的PPT上給的最大勢算法（MCS）求完美消除序列。前前后后sumbit了19次，為WA提供了大量分母啊。。。。 多寫點為自己備份吧。
2 有用的資料：
3 定理：一個圖是弦圖當(dāng)且僅當(dāng)它有一個完美消除序列。所以要先搞到完美消除序列：
4 如何判斷搞到的是不是完美消除序列：
#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;
}
1 弦圖，看了一個周末有木有！太弱了點，算法完全按照CDQ的PPT上給的最大勢算法（MCS）求完美消除序列。前前后后sumbit了19次，為WA提供了大量分母啊。。。。 多寫點為自己備份吧。
2 有用的資料：
3 定理：一個圖是弦圖當(dāng)且僅當(dāng)它有一個完美消除序列。所以要先搞到完美消除序列：
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)文章
這篇文章主要介紹了c語言中的二級指針做函數(shù)參數(shù)說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-05-05
布爾型（Boolean），是一種類型變量類型，引用（reference）就是C++對C語言的重要擴充。引用就是某一變量（目標(biāo)）的一個別名，對引用的操作與對變量直接操作完全一樣2022-04-04
C++中回調(diào)函數(shù)及函數(shù)指針的實例詳解
這篇文章主要介紹了C++中回調(diào)函數(shù)及函數(shù)指針的實例詳解的相關(guān)資料,希望通過本文能幫助到大家，讓大家理解掌握這部分內(nèi)容，需要的朋友可以參考下2017-10-10
C++ Qt開發(fā)之使用QProcess實現(xiàn)進(jìn)程管理
Qt 是一個跨平臺C++圖形界面開發(fā)庫,利用Qt可以快速開發(fā)跨平臺窗體應(yīng)用程序,本文將重點介紹如何運用QProcess組件實現(xiàn)針對進(jìn)程的控制管理等,感興趣的可以了解下2024-03-03
C++數(shù)據(jù)結(jié)構(gòu)之搜索二叉樹的實現(xiàn)
了解搜索二叉樹是為了STL中的map和set做鋪墊，我們所熟知的AVL樹和平衡搜索二叉樹也需要搜索二叉樹的基礎(chǔ)。本文將詳解如何利用C++實現(xiàn)搜索二叉樹，需要的可以參考一下2022-05-05
這篇文章主要為大家詳細(xì)介紹了如何基于C/C++實現(xiàn)一個簡單的詞法分析程序，并通過完成詞法分析程序，了解詞法分析的過程，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)學(xué)習(xí)2023-05-05
Qt創(chuàng)建項目實戰(zhàn)之手把手創(chuàng)建第一個Qt項目
我們在進(jìn)行軟件開發(fā)學(xué)習(xí)時,有時候需要qt軟件進(jìn)行代碼的敲寫,下面這篇文章主要給大家介紹了關(guān)于Qt創(chuàng)建項目實戰(zhàn)之手把手創(chuàng)建第一個Qt項目的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-04-04
C語言返回字符串函數(shù)共有四種方式，分別如下：使用堆空間，返回申請的堆地址，注意釋放、函數(shù)參數(shù)傳遞指針，返回該指針、返回函數(shù)內(nèi)定義的靜態(tài)變量（共享）、返回全局變量2017-05-05
本文將詳細(xì)介紹NSString與C字符串之間的相互轉(zhuǎn)換，需要的朋友可以參考下2012-11-11
這篇文章主要給大家介紹了關(guān)于C++ string字符串修改與替換方法的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12