久久国产精品久久精品国产,人妻无码久久一区二区三区免费 ,中文字幕无码久久精品青草

P1094

拓撲排序..
這個真是WA了n多次..orz..
總之就是有很多細節..因為結果的可能性太多..而樣例實在是只給了太少的可能性- -..

#include <iostream>

#include <queue>

#include <string>

using namespace std;

int n,m;

const int MAXN=27;

bool edge[MAXN][MAXN];

int d[MAXN];

int state;

void jude(int ix)

{

state=0;

string str="";

int count=0;

queue<int> q;

int u[MAXN];

for (int i=1;i<=n;i++)

{

u[i]=d[i];

// cout<<u[i]<<endl;

if (0==d[i]) q.push(i);

}

if (q.size()>1) {state=3;}

while(q.size()>0)

{

int v=q.front();

int c_ount=0;

for (int i=1;i<=n;i++)

if (edge[i][v])

{

u[i]--;

if (0==u[i]) {c_ount++;q.push(i);}

}

if (c_ount>1) {state=3;}

q.pop();count++;str=char(v+64)+str;

}

// cout<<count<<" "<<n<<endl;

if (count<n)

{

cout<<"Inconsistency found after "<<ix<<" relations."<<endl;

state=2;return;

}

if (state==3) return;

cout<<"Sorted sequence determined after "<<ix<<" relations: ";

cout<<str<<"."<<endl;

state=1;return;

}

int main()

{

while(1)

{

memset(edge,0,sizeof(edge));

memset(d,0,sizeof(d));

state=0;

cin>>n>>m;

if (0==n&&0==m) break;

char str[3];

for (int i=1;i<=m;i++)

{

cin>>str;

if (state==1) continue;

if (state==2) continue;

int x=int(str[0])-64;

int y=int(str[2])-64;

if (edge[x][y]) continue;

d[x]=d[x]+1;

edge[x][y]=true;

jude(i);

}

if (state==3) cout<<"Sorted sequence cannot be determined."<<endl;

}

return 0;

}

posted on 2009-10-07 18:25 Vincent 閱讀(137) 評論(0) 編輯收藏引用所屬分類: 數據結構與算法

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: P3368 P2352 dinic P3273 P2104 ctsc2000 丘比特的煩惱 usaco 4.3 lgame P3267 P1276 P1837

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

巢穴

My Links

Blog Stats

News

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

文章檔案

Link

搜索

最新評論

閱讀排行榜

評論排行榜

P1094