久久国产精品久久国产精品,久久93精品国产91久久综合,久久福利青草精品资源站

P2513

trie+并查集+歐拉回路
有空數據..其實沒影響..但是討論里有個人說空數據輸出Impossible...其實應該Possible...
這個人太邪惡了..
另外用數組寫tire,re了不下5次..
最后改成了動態的..
1000+ms..還是挺慢的..

#include <iostream>

#include <stdio.h>

#include <string>

using namespace std;

struct node

{

node *s[26];

int count;

int pos;

node()

{

count=0;

pos=0;

for(int i=0;i<26;i++)

s[i]=NULL;

}

}*root;

int f[500010],o[500010];

int len=0,l=0;

char st1[11];

char st2[11];

int insert(char *ch)

{

int ts=0;

node *p=root;

for (int i=0;i<strlen(ch);i++)

{

if ((p->s[ch[i]-'a'])==NULL)

{

p->s[ch[i]-'a']=new node();

}

p=p->s[ch[i]-'a'];

}

if (p->count==0)

{

len++;

p->count=1;

p->pos=len;

ts=len;

return ts;

}

else

{

ts=p->pos;

return ts;

}

int getfather(int x)

{

if (f[x]==x) return x;

f[x]=getfather(f[x]);

return f[x];

}

int main()

{

for (int i=0;i<500010;i++)

{f[i]=i;o[i]=0;}

root=new node();

int u=0;

while(scanf ("%s %s", st1, st2) != EOF)

{

u++;

int x=insert(st1);

int y=insert(st2);

int fx=getfather(x);

int fy=getfather(y);

o[x]++;

o[y]++;

if (fx!=fy) f[fy]=fx;

// if (u==5) break;

}

int itn=0;

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

if (getfather(i)==i) itn++;

int odd=0;

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

if (o[i]%2) odd++;

if (len==0)

{

cout<<"Possible"<<endl;

exit(0);

}

if (itn==1&&(odd==2||odd==0))

{

cout<<"Possible"<<endl;

}

else

{

cout<<"Impossible"<<endl;

}

// system("pause");

return 0;

}

posted on 2009-11-03 16:59 Vincent 閱讀(96) 評論(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

搜索

最新評論

閱讀排行榜

評論排行榜

P2513