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