亚洲国产婷婷香蕉久久久久久,久久国产精品久久国产精品,精品国产乱码久久久久久人妻

POJ 3187 (next_permutation)

摘要: 用了STL_algorithm中的permution，很好很強大！閱讀全文

posted @ 2008-10-22 17:25 Torres 閱讀(631) | 評論 (1) | 編輯收藏

POJ 2502 Floyd

摘要: 自己寫了一個，不過貼一個Waterloo的標程，突然喜歡上這種風格了，求最短路的！閱讀全文

posted @ 2008-10-20 22:25 Torres 閱讀(268) | 評論 (0) | 編輯收藏

POJ 1094 Topological_Sort（拓撲排序）

摘要: wa的不行，改了又改，亂套了，最后重寫ac了！閱讀全文

posted @ 2008-10-20 22:18 Torres 閱讀(347) | 評論 (0) | 編輯收藏

拓撲排序—數據結構嚴蔚敏p173

//基于AOV(activity on vertex)網絡的拓撲排序

#include<iostream>

#include<string>

#include<algorithm>

#include<vector>

using namespace std;

#define VN 20

vector<int> p[VN];

int de[VN];

int main()

{

int i,j,s,e;

int n;

int re[VN];

memset(de,0,sizeof(de));

freopen("in.txt","r",stdin);

scanf("%d",&n);

while(scanf("%d%d",&s,&e))

{

if(s==0&&e==0) break;

p[s].push_back(e);

de[e]++;

}

int k=0;

int flag;

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

{

flag=0;

for(j=1;j<=n;j++)

if(de[j]==0)

{

re[k++]=j;

int len=p[j].size();

for(int t=0;t<len;t++)

de[p[j][t]]--;

de[j]=-1;

flag=1;

break;

}

if(!flag) break;

}

if(k<n) printf("Can't do it\n");

else

{

for(i=0;i<n;i++)

printf("%d ",re[i]);

printf("\n");

}

return 0;

}

測試結果：
8
2 1
3 2
2 4
5 4
7 8
1 8
8 3
3 6
4 8
4 6
0 0
Can't do it

8
2 1
2 3
2 4
5 4
7 8
1 8
3 8
3 6
4 8
4 6
0 0
2 1 3 5 4 6 7 8

posted @ 2008-10-19 10:45 Torres 閱讀(262) | 評論 (0) | 編輯收藏

POJ3253(赫夫曼樹)

摘要: 很久以前做得題，感覺很huffman 閱讀全文

posted @ 2008-10-16 21:23 Torres 閱讀(316) | 評論 (0) | 編輯收藏

pku 1269 (平面兩直線的位置關系)

摘要: 幾何題，高中數學，告誡自己細心一點兒，耐心一點兒！閱讀全文

posted @ 2008-09-24 21:29 Torres 閱讀(236) | 評論 (0) | 編輯收藏

判斷點是否在多邊形中

我就叫他射線法吧
基本步驟：

１，過ｐ點垂直向上作一條射線

２，判斷此射線與ｎ邊形ｎ條邊的交點

３，把所有交點相加，如果是奇數則說明在多邊形內，否則在多邊形外

思路非常的簡單，另外說明一下幾種特殊的情況：

１，射線與多邊形的頂點相交；比如射線過多邊形的Pi點，則如果Pi-1和Pi+1在此射線的異側，此交點可以算一個，如果此兩點在射線的同側，則此交點不計。此結論非常簡單，畫個圖應該就能明白了

２，ｐ點在多邊形的某一條邊上；也認為ｐ在多邊形中

３，ｐ不在多邊形的邊上，但ｐ的射線與多邊形的某一條邊重合；比如與Pi,Pi+1線段重合，則如果Pi-1和Pi+2在射線的兩側，此情況也算一個交點，否則此情況不計交點

posted @ 2008-09-23 20:51 Torres 閱讀(522) | 評論 (0) | 編輯收藏

POJ 1511(spfa)

摘要: The first SPFA 閱讀全文

posted @ 2008-09-12 11:17 Torres 閱讀(505) | 評論 (0) | 編輯收藏

SPFA (Shortest Path Faster Algorithm)

摘要: 網上看到的spfa的實現，很清晰。Orz~~ #include <cstdio>#include <cstring>const int maxn = 10000+1;const int maxnm = 100000+1;class node { ... 閱讀全文

posted @ 2008-09-11 17:01 Torres 閱讀(1087) | 評論 (2) | 編輯收藏

POJ 1256(全排列——next_permutation)

這里有對全排列函數permutation的介紹http://hi.baidu.com/sunshine_0316/blog/item/6f87a044bf30f320cffca381.html

#include<iostream>

#include<map>

#include<algorithm>

using namespace std;

typedef struct node

{

char ch;

int flag;

}node;

bool cmp(const node a,const node b)

{

return a.flag<b.flag;

}

int main()

{

int cas,i;

char str[15],ch;

map<char,int> mp;

for(ch='A',i=1;ch<='Z';ch++,i=i+2) mp[ch]=i;

for(ch='a',i=2;ch<='z';ch++,i=i+2) mp[ch]=i;

scanf("%d",&cas);

while(cas--)

{

scanf("%s",str);

int len=strlen(str);

node p[15];

for(i=0;i<len;i++)

{

p[i].ch=str[i];

p[i].flag=mp[str[i]];

}

sort(p,p+len,cmp);

do

{

for(i=0;i<len;i++)

printf("%c",p[i].ch);

printf("\n");

}while(next_permutation(p,p+len,cmp));

}

return 0;

}

posted @ 2008-09-10 11:32 Torres 閱讀(991) | 評論 (0) | 編輯收藏

T9的空間

公告

隨筆分類

隨筆檔案

相冊

收藏夾

我的鏈接

搜索

積分與排名

最新隨筆

最新評論