T9的空间

You will never walk alone!
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  69 随笔 :: 0 文章 :: 28 评论 :: 0 Trackbacks

#

POJ 3187 (next_permutation)
     摘要: 用了STL_algorithm中的permution，很好很强大！  阅读全文
posted @ 2008-10-22 17:25 Torres 阅读(616) | 评论 (1) | 编辑 收藏

POJ 2502 Floyd
     摘要: 自己写了一个，不过贴一个Waterloo的标程，突然喜欢上这种风格了，求最短路的！  阅读全文
posted @ 2008-10-20 22:25 Torres 阅读(253) | 评论 (0) | 编辑 收藏

POJ 1094 Topological_Sort（拓扑排序）
     摘要: wa的不行，改了又改，乱套了，最后重写ac了！  阅读全文
posted @ 2008-10-20 22:18 Torres 阅读(321) | 评论 (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 阅读(237) | 评论 (0) | 编辑 收藏

POJ3253(赫夫曼树)
     摘要: 很久以前做得题，感觉很huffman  阅读全文
posted @ 2008-10-16 21:23 Torres 阅读(291) | 评论 (0) | 编辑 收藏

pku 1269 (平面两直线的位置关系)
     摘要: 几何题，高中数学，告诫自己细心一点儿，耐心一点儿！  阅读全文
posted @ 2008-09-24 21:29 Torres 阅读(218) | 评论 (0) | 编辑 收藏

判断点是否在多边形中

我就叫他射线法吧
基本步骤：

１，过ｐ点垂直向上作一条射线

２，判断此射线与ｎ边形ｎ条边的交点

３，把所有交点相加，如果是奇数则说明在多边形内，否则在多边形外

思路非常的简单，另外说明一下几种特殊的情况：

１，射线与多边形的顶点相交；比如射线过多边形的Pi点，则如果Pi-1和Pi+1在此射线的异侧，此交点可以算一个，如果此两点在射线的同侧，则此交点不计。此结论非常简单，画个图应该就能明白了

２，ｐ点在多边形的某一条边上；也认为ｐ在多边形中

３，ｐ不在多边形的边上，但ｐ的射线与多边形的某一条边重合；比如与Pi,Pi+1线段重合，则如果Pi-1和Pi+2在射线的两侧，此情况也算一个交点，否则此情况不计交点

posted @ 2008-09-23 20:51 Torres 阅读(497) | 评论 (0) | 编辑 收藏

POJ 1511(spfa)
     摘要: The first SPFA  阅读全文
posted @ 2008-09-12 11:17 Torres 阅读(488) | 评论 (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 阅读(1065) | 评论 (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 阅读(947) | 评论 (0) | 编辑 收藏

仅列出标题
共7页: 1 2 3 4 5 6 7