C++博客-lzm

poj 1094 Sorting It All Out

lzmagic — Sun, 12 Apr 2009 15:13:00 GMT

    wa了很多次，终于过了，咔咔~笑一下先。
    第一次很快用拓扑排序把代码敲出来，提交，wa，仔细分析后，发现忽略了重复边的情况，插入边(u, v)，如果图g已经存在了边(u,v)，就不能再增加v的入度。
    很快改过来，提交，还是wa，很无奈，上网看看大牛评论，原来是只要当前输入数据能“确定唯一”，及时后面输入数据“有环”，也是判定为“确定唯一”。也就是说，每输入一条边，如果判定有结果，忽略后面输入数据，即使后面输入数据能改变结果。
    再改，再提交，还是wa，几度欲放弃之，还是坚持下来了，上google找别人代码来分析，结果发选只要当前输入数据“有环”，及时当前输入数据“不能确定唯一”，也是判定为“有环”。
    把判定顺序改过后，提交，终于ac!!!
    呼~~~爽YY中……

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
#include <ctime>
#include <cstdlib>
#include <cctype>
using namespace std;

#define UNSURE 0 // 不能确定
#define CYCLED 1 // 存在回路
#define SORTED 2 // 已经排序

int n;                            // n ：顶点个数
vector<list<int> > g;           // g ：图
vector<int> top;                // top ：拓扑序列
vector<int> ins;                // ins ：入度

int Topsort()
{
    bool unsure(false);
    queue<int> que;
    vector<int> cnt(ins.begin(), ins.end());    // 用cnt存储ins，避免修改ins。
    for (int j = 0; j < n; ++j)
        if (cnt[j] == 0) que.push(j);            // 入度为0的顶点入队。
    int u;
    list<int>::iterator it;
    top.clear();
    while (!que.empty())
    {
        if (que.size() != 1) unsure = true;        // 如果选择顶点多余1个，不能确定。
        u = que.front(); que.pop();
        top.push_back(u);
        for (it = g[u].begin(); it != g[u].end(); ++it)
            if (--cnt[*it] == 0) que.push(*it);
    }
    if (top.size() != n) return CYCLED;        // 先判断是否有环，即使不能确定，
    if (unsure) return UNSURE;                // 再判断是否不能确定。
    return SORTED;
}

int main()
{
    int steps, ans;
    string exp;
    int m, u, v, i;

    while (cin >> n >> m, n != 0 || m != 0)    // 2 <= n <= 26
    {
        g.assign(n, list<int>());
        ins.assign(n, 0);
        ans = UNSURE;
        for (steps = 0; ans == UNSURE && steps < m; ++steps)
        {
            cin >> exp;
            u = int(exp[0] - 'A'), v = int(exp[2] - 'A');
            if (find(g[u].begin(), g[u].end(), v) == g[u].end()) // 如果不存在边(u, v)，添加。
                g[u].push_back(v), ++ins[v];
            ans = Topsort();
        }
        for (i = steps; i < m; ++i) cin >> exp; // 处理剩下无用的输入数据。

        if (ans == UNSURE) // Output()
            cout << "Sorted sequence cannot be determined." << endl;
        else if (ans == CYCLED)
            cout << "Inconsistency found after " << steps << " relations." << endl;
        else
        {
            cout << "Sorted sequence determined after " << steps << " relations: ";
            for (i = 0; i < n; i++) cout << char('A' + top[i]);
            cout << "." << endl;
        } // end Output()
    }
    system("pause");
    return 0;
}

ps.第一，要仔细看题，第二，还是要仔细看题。

lzmagic 2009-04-12 23:13 发表评论

Floyd_Warshall算法

lzmagic — Fri, 10 Apr 2009 19:14:00 GMT

/**
* FLOYD_WARSHALL 所有顶点对的最短路径算法 (All-Pairs Shortest Path Algorithm)
* 输入：图g
* 输出：所有顶点对的最短路径长
* 结构：图g用邻接矩阵表示
* 算法：Floyd_Warshall算法(动态规划)
* 复杂度：O(|V|^3)
*/
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <stack>
#include <queue>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;

int n;
vector<vector<int> > g;
vector<vector<int> > dist;

void Floyd_Warshall()
{
    // 初始化dist，顶点间(无中间顶点)最短路径长为边长，顶点到自身的最短路径长为0。
    dist = g;
    for (int i = 0; i < n; ++i)
        dist[i][i] = 0;
    // 从顶点i到定点j且中间顶点皆属于集合{0, 1, 2, , k}的最短路径长。
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (dist[i][k] < INT_MAX && dist[k][j] < INT_MAX)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

int main()
{
    n = 5;
    g.assign(n, vector<int>(n, INT_MAX));
    g[0][1] = 3; g[0][2] = 8; g[0][4] = -4;
    g[1][3] = 1; g[1][4] = 7;
    g[2][1] = 4;
    g[3][0] = 2; g[3][2] = -5;
    g[4][3] = 6;

    Floyd_Warshall();

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
            cout << dist[i][j] << ' ';
        cout << endl;
    }

    system("pause");
    return 0;
}

lzmagic 2009-04-11 03:14 发表评论

Kruskal算法

lzmagic — Fri, 10 Apr 2009 11:41:00 GMT

/**
* KRUSKAL 最小生成树算法 (Minimum Spanning Tree)
* 输入：图g；                 // 有向图或者无向图
* 输出：(1)最小生成树长sum；
*         (2)最小生成树mst。
* 结构: 图g用顶点数n和边集edges(优先队列)表示，两点是否连通用并查集实现。
* 算法：Kruskal算法
* 复杂度：O(|E|*log|E|)~O(|E|*log|V|)
*/
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;

struct Edge
{
    int u, v, w;        // u、v:两个顶点  w:权
    Edge() { }
    Edge(int u0, int v0, int w0):u(u0), v(v0), w(w0) { }
};

int n;                    // n : 顶点个数
vector<Edge> edges;        // edges : 图g的所有边
int sum;                // sum : 最小生成树长
vector<Edge> mst;        // mst : 最小生成树(用边集表示)

class DisjSets
{
    vector<int> s;
    public:
        DisjSets(int n) : s(n, -1) { };
        int find (int x)
        {
            if (s[x] < 0) return x;
            else return s[x] = find(s[x]);   // 压缩路径。
        };
        void unionSets(int root1, int root2)
        {
            if (s[root1] > s[root2])    // 按个数求并(个数用负数表示)。
            {
                s[root2] += s[root1];
                s[root1] = root2;
            }
            else
            {
                s[root1] += s[root2];
                s[root2] = root1;
            }
        };
};

bool Cmp(const Edge &lhs, const Edge &rhs)
{
    return lhs.w > rhs.w;
}

bool Kruskal()
{
    DisjSets ds(n);
    make_heap(edges.begin(), edges.end(), Cmp);    // 对边集建堆。
    int root1, root2;
    Edge e;
    while (!edges.empty())    // 遍历所有边，
    {
        e = edges.front(); pop_heap(edges.begin(), edges.end(), Cmp); edges.pop_back();// 从未选边集中寻找最小权的边e。
        root1 = ds.find(e.u), root2 = ds.find(e.v);    // 获取u、v所在的点集，
        if (root1 != root2)                // 如果u、v不是同一个点集，
        {
            sum += e.w;                 // 调整最小生成树长
            mst.push_back(e);             // 把边e放入最小生成树mst中，
            ds.unionSets(root1, root2);    // 合并两点所在的点集。
        }
        if (mst.size() == n - 1) return true; // 如果选取边个数为n - 1，成功。
    }
    return false;
}

int main()
{
    n = 7;
    edges.clear();
    edges.push_back(Edge(0, 1, 2)); edges.push_back(Edge(0, 2, 4));  edges.push_back(Edge(0, 3, 1));
    edges.push_back(Edge(1, 3, 3)); edges.push_back(Edge(1, 4, 10));
     edges.push_back(Edge(2, 3, 2)); edges.push_back(Edge(2, 5, 5));
     edges.push_back(Edge(3, 4, 7)); edges.push_back(Edge(3, 5, 8)); edges.push_back(Edge(3, 6, 4));
     edges.push_back(Edge(4, 6, 6));
     edges.push_back(Edge(5, 6, 1));

     sum = 0;
     mst.clear();
     if(Kruskal())
     {
        cout << sum << endl;
        for (vector<Edge>::iterator it = mst.begin(); it != mst.end(); ++it)
            cout << it->u << "->" << it->v << endl;
    }
    else
    {
        cout << "Some vertex cann't be reached." << endl;
    }

    system("pause");
    return 0;
}

lzmagic 2009-04-10 19:41 发表评论

Prim算法

lzmagic — Fri, 10 Apr 2009 11:11:00 GMT

/**
* PRIM(简单版) 最小生成树算法 (Minimum Spanning Tree)
* 输入：图g；                 // 有向图或者无向图
* 输出：(1)最小生成树长sum；
*         (2)最小生成树prev。
* 结构: 图g用邻接矩阵表示，最短边长dist用数组表示。
* 算法：Prim算法
* 复杂度：O(|V|^2)
*/
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;

int n;                    // n : 顶点个数
vector<vector<int> > g; // g : 图(graph)(用邻接矩阵(adjacent matrix)表示)
vector<bool> known;        // known : 各点是否已经选取
vector<int> dist;        // dist : 已选取点集到未选取点的最小边长
vector<int> prev;        // prev : 最小生成树中各点的前一顶点
int s;                    // s : 起点(start)
int sum;                // sum : 最小生成树长

bool Prim()                // 贪心算法(Greedy Algorithm)
{
    known.assign(n, false);
    dist.assign(n, INT_MAX);
    prev.resize(n);            // 初始化known、dist、prev。
    dist[s] = 0;            // 初始化起点到自身的路径长为0。
    int i;
    for (i = 0; i < n; ++i)
    {
        int min = INT_MAX, v;
        for (int i = 0; i < n; ++i)
            if (!known[i] && min > dist[i])
                min = dist[i], v = i;    // 寻找未知的最短路径长的顶点v，
        if (min == INT_MAX) break;        // 如果找不到，退出；
        known[v] = true;                // 如果找到，将顶点v设为已知，
        sum += dist[v];                 // 调整最小生成树长
        for (int w = 0; w < n; ++w)        // 遍历所有v指向的顶点w，
            if (!known[w] && g[v][w] < INT_MAX && dist[w] > g[v][w])
                dist[w] = g[v][w], prev[w] = v;    // 调整顶点w的最短路径长dist和最短路径的前一顶点 prev。
    }
    return i == n; // 如果选取顶点个数为n，成功。
}

int main()
{
    n = 7;
    g.assign(n, vector<int>(n, INT_MAX));
    g[0][1] = g[1][0] = 2; g[0][2] = g[2][0] = 4;   g[0][3] = g[3][0] = 1;
    g[1][3] = g[3][1] = 3; g[1][4] = g[4][1] = 10;
    g[2][3] = g[3][2] = 2; g[2][5] = g[5][2] = 5;
    g[3][4] = g[4][3] = 7; g[3][5] = g[5][3] = 8; g[3][6] = g[6][3] = 4;
    g[4][6] = g[6][4] = 6;
    g[5][6] = g[6][5] = 1;

    s = 0;        // 起点任选
    sum = 0;
    if (Prim())
    {
        cout << sum << endl;
        for (int i = 1; i < n; ++i)
            if(i != s) cout << prev[i] << "->" << i << endl;
    }
    else
    {
        cout << "Some vertex cann't be reached." << endl;
    }

    system("pause");
    return 0;
}

lzmagic 2009-04-10 19:11 发表评论

Critical Path 关键路径

lzmagic — Thu, 09 Apr 2009 15:02:00 GMT

摘要: /**//** * CRITICALPATH(简单版) 关键路径 * 输入：无环图g。 * 输出：(1)各点最早完成时间ec； * (2)各点最晚完成时间lc； * &n... 阅读全文

lzmagic 2009-04-09 23:02 发表评论

Bellman_Ford算法 SPFA算法

lzmagic — Thu, 09 Apr 2009 11:16:00 GMT

摘要: /**//** * BELLMAN_FORD (简单版) 单源最短路径算法（允许存在负边） * 输入：(1)有向图g； * (2)源点s。 * 输出：(1)源点s到各点的最短路径长... 阅读全文

lzmagic 2009-04-09 19:16 发表评论

Dijkstra算法

lzmagic — Thu, 09 Apr 2009 02:45:00 GMT

/**
* DIJKSTRA(简单版) 单源最短路径算法（不允许存在负边）
* 输入：(1)图g；        // 有向图或者无向图
*         (2)源点s。
* 输出：(1)源点s到各点的最短路径长dist；
*         (2)源点s到各点的最短路径prev。
* 结构: 图g用邻接矩阵表示，最短路径长dist用数组表示。
* 算法：Dijkstra算法
* 复杂度：O(|V|^2)
*/
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;

int n;                    // n : 顶点个数
vector<vector<int> > g; // g : 图(graph)(用邻接矩阵(adjacent matrix)表示)
int s;                    // s : 源点(source)
vector<bool> known;        // known : 各点是否知道最短路径
vector<int> dist;        // dist : 源点s到各点的最短路径长
vector<int> prev;        // prev : 各点最短路径的前一顶点

void Dijkstra()            // 贪心算法(Greedy Algorithm)
{
    known.assign(n, false);
    dist.assign(n, INT_MAX);
    prev.resize(n);            // 初始化known、dist、prev。
    dist[s] = 0;            // 初始化源点s到自身的路径长为0。
    for (;;)
    {
        int min = INT_MAX, v = s;
        for (int i = 0; i < n; ++i)
            if (!known[i] && min > dist[i])
                min = dist[i], v = i;    // 寻找未知的最短路径长的顶点v，
        if (min == INT_MAX) break;        // 如果找不到，退出；
        known[v] = true;                // 如果找到，将顶点v设为已知，
        for (int w = 0; w < n; ++w)        // 遍历所有v指向的顶点w，
            if (!known[w] && g[v][w] < INT_MAX && dist[w] > dist[v] + g[v][w])
                dist[w] = dist[v] + g[v][w], prev[w] = v;    // 调整顶点w的最短路径长dist和最短路径的前一顶点 prev。
    }
}

void Print_SP(int v)
{
     if (v != s) Print_SP(prev[v]);
     cout << v << " ";
}

int main()
{
    n = 7;
    g.assign(n, vector<int>(n, INT_MAX));
    g[0][1] = 2; g[0][3] = 1;
    g[1][3] = 3; g[1][4] = 10;
    g[2][0] = 4; g[2][5] = 5;
    g[3][2] = 2; g[3][4] = 2; g[3][5] = 8; g[3][6] = 4;
    g[4][6] = 6;
    g[6][5] = 1;

    s = 0;
    Dijkstra();

    copy(dist.begin(), dist.end(), ostream_iterator<int>(cout, " ")); cout << endl;
    for (int i = 0; i < n; ++i)
        if(dist[i] != INT_MAX)
        {
            cout << s << "->" << i << ": ";
            Print_SP(i);
            cout << endl;
        }

    system("pause");
    return 0;
}

lzmagic 2009-04-09 10:45 发表评论

USP 无权最短路径算法

lzmagic — Thu, 09 Apr 2009 02:44:00 GMT

/**
* USP 无权最短路径算法(Unweighted Shortest Path Algorithm)
* 输入：(1)图g；        // 有向图或者无向图
*         (2)源点s。
* 输出：(1)源点s到各点的无权最短路径长dist(路径的边数最小)；
*         (2)源点s到各点的无权最短路径prev。
* 结构: 图g用邻接表表示，最短路径长dist用数组表示。
* 算法：广度优先搜索(BFS)
* 复杂度：O(|E|+|V|)~O(|E|)
*/
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;

int n;                        // n : 顶点个数
vector<list<int> > g;        // g : 图(graph)(用邻接表(adjacent list)表示)
int s;                        // s : 源点(source)
vector<int> dist;            // dist : 源点s到各点之间的距离
vector<int> prev;            // prev : 各点最短路径的前一顶点号

void USP()        // 广度优先搜索(BFS)
{
    queue<int> que;
    dist.assign(n, INT_MAX);                     // 初始化dist，
    prev.resize(n);                                // 初始化prev。
    dist[s] = 0; que.push(s);                    // s到自身距离为0，s入队。
    while (!que.empty())
    {
        int v = que.front(); que.pop();            // v出队，
        for (list<int>::iterator it = g[v].begin(); it != g[v].end(); ++it) // 遍历v相邻点*it，
            if (dist[*it] == INT_MAX)            // 如果*it未访问，
            {
                dist[*it] = dist[v] + 1; prev[*it] = v;    // 调整点*it，
                que.push(*it);                    // *it入队。
            }
    }
}

void Print_SP(int v)
{
     if (v != s) Print_SP(prev[v]);
     cout << v << " ";
}

int main()
{
    n = 7;
    g.assign(n, list<int>());
    g[0].push_back(1); g[0].push_back(3);
    g[1].push_back(3); g[1].push_back(4);
    g[2].push_back(0); g[2].push_back(5);
    g[3].push_back(2); g[3].push_back(4); g[3].push_back(5); g[3].push_back(6);
    g[4].push_back(6);
    g[6].push_back(5);

    s = 2;
    USP();

    copy(dist.begin(), dist.end(), ostream_iterator<int>(cout, " ")); cout << endl;
    for (int i = 0; i < n; ++i)
        if(dist[i] != INT_MAX)
        {
            cout << s << "->" << i << ": ";
            Print_SP(i);
            cout << endl;
        }

    system("pause");
    return 0;
}

lzmagic 2009-04-09 10:44 发表评论

Topsort 拓扑排序

lzmagic — Mon, 06 Apr 2009 01:40:00 GMT

/**
* TOPSORT(简单版) 拓扑排序(Topological Sort)
* 输入：有向图g
* 输出：是否存在拓扑排序，如果存在，获取拓扑排序序列seq
* 结构：图g用邻接矩阵表示
* 算法：广度优先搜索(BFS)
* 复杂度：O(|V|^2)
*/

#include <iostream>
#include <vector>
#include <queue>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <climits>
using namespace std;

int n;                            // n ：顶点个数
vector<vector<int> > g;           // g ：图(graph)(用邻接矩阵(adjacent matrix)表示)
vector<int> seq;                // seq ：拓扑序列(sequence)

bool TopSort()
{
    vector<int> inc(n, 0);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
             if (g[i][j] < INT_MAX) ++inc[j]; // 计算每个顶点的入度，
    queue<int> que;
    for (int j = 0; j < n; ++j)
        if (inc[j] == 0) que.push(j); // 如果顶点的入度为0，入队。
    int seqc = 0;
    seq.resize(n);
    while (!que.empty())     // 如果队列que非空，
    {
        int v = que.front(); que.pop();
        seq[seqc++] = v;      // 顶点v出队，放入seq中，
        for (int w = 0; w < n; ++w)     // 遍历所有v指向的顶点w，
            if (g[v][w] < INT_MAX)
                if (--inc[w] == 0) que.push(w); // 调整w的入度，如果w的入度为0，入队。
    }
    return seqc == n; // 如果seq已处理顶点数为n，存在拓扑排序，否则存在回路。
}

int main()
{
    n = 7;
    g.assign(n, vector<int>(n, INT_MAX));
    g[0][1] = 1, g[0][2] = 1, g[0][3] = 1;
    g[1][3] = 1, g[1][4] = 1;
    g[2][5] = 1;
    g[3][2] = 1, g[3][5] = 1, g[3][6] = 1;
    g[4][3] = 1, g[4][6] = 1;
    g[6][5] = 1;

    if (TopSort())
    {
         copy(seq.begin(), seq.end(), ostream_iterator<int>(cout, " "));
         cout << endl;
    }
    else
    {
         cout << "circles exist" << endl;
    }

    system("pause");
    return 0;
}

lzmagic 2009-04-06 09:40 发表评论

(正则表达式)是否匹配(字符串)

lzmagic — Sat, 04 Apr 2009 14:58:00 GMT

/**
* IS_MATCHED
* 输入：(1)一个正则表达式：带有正则符号'*'、'+'、'?'、'.'(正则符号不相邻)；
*          '*'：任意多个任意字符；
*          '+'：至少1个任意字符；
*          '?'：0个或1个任意字符；
*          '.'：恰好1个任意字符。
*       (2)一个字符串。
* 输出：该正则表达式是否匹配该字符。
*/
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

bool Is_Matched(string &reg, string &str)
{
     bool is_asterisk, is_plus, is_question, is_dot, is_ok(true);
     string substr;
     string::iterator reg_it(reg.begin()), str_it(str.begin()), str_it2;
     while (is_ok && reg_it != reg.end())
     {
         // 分离正则符号给is_asterisk、is_plus、is_question、is_dot。
         is_asterisk = *reg_it == '*';
         is_plus     = *reg_it == '+';
         is_question = *reg_it == '?';
         is_dot      = *reg_it == '.';
         if ( is_asterisk || is_plus || is_question || is_dot) ++reg_it;
         // 分离子字符串给substr。
         substr.clear();
         for (reg_it = reg_it; reg_it != reg.end()
                           && *reg_it != '*'
                           && *reg_it != '+'
                           && *reg_it != '?'
                           && *reg_it != '.'; ++reg_it)// 调整reg_it。
             substr.push_back(*reg_it);
         // 匹配子字符串：substr空，str_it2=>end()，否则str_it2=>匹配点或end()。
         if (substr.empty()) str_it2 = str.end();
         else str_it2 = search(str_it, str.end(), substr.begin(), substr.end());
         // 是否匹配正则符号：is_asterisk不做判断。
         if (is_plus     && str_it ==  str_it2
          || is_question && str_it != str_it2 && str_it != str_it2 - 1
          || is_dot      && str_it != str_it2 - 1) is_ok = false;
         // 是否匹配子字符串。
         if (!substr.empty() && str_it2 == str.end()) is_ok = false;
         else str_it = str_it2 + substr.size();       // 调整str_it。
     }
     // 匹配成功：is_ok为true，reg_it到达reg.end()，str_it到达str.end()。
     return is_ok && reg_it == reg.end() && str_it == str.end();
}

int main ()
{
    string reg, str; // input : *l?m.g+ lzmagic ?zm lzmagic
    while (cin >> reg >> str)
    {
          if (Is_Matched(reg, str)) cout << "match" << endl;
          else cout << "dismatch" << endl;
    }

    system("pause");
    return 0;
}

lzmagic 2009-04-04 22:58 发表评论

Quicksort 快速排序

lzmagic — Fri, 03 Apr 2009 01:53:00 GMT

/**
* QUICKSORT : sort
*        void sort(iterator beg, iterator end);
*        void sort(iterator beg, iterator end, compare cmp);
*/
#include <iostream>
#include <iterator>
#include <algorithm>
#include <numeric>
using namespace std;

int Partition(int *a, int lhs, int rhs)
{
       int key = a[rhs];
       int i = lhs - 1;
       for (int j = lhs; j < rhs; ++j)
             if (a[j] <= key) swap(a[++i], a[j]);
       swap(a[++i], a[rhs]);
       return i;
}

void QuickSort(int *a, int lhs, int rhs)
{
      if (lhs < rhs)
      {
             int mid = Partition(a, lhs, rhs);
             QuickSort(a, lhs, mid - 1);
             QuickSort(a, mid + 1, rhs);
      }
}

int main()
{
    int a[100];
    for (int i = 0; i < 100; ++i) a[i] = i;
    random_shuffle(a, a + 100);
    copy(a, a + 100, ostream_iterator<int>(cout, " ")); cout << endl << endl;

    QuickSort(a, 0, 99);
    copy(a, a + 100, ostream_iterator<int>(cout, " ")); cout << endl;

    system("pause");
    return 0;
}

lzmagic 2009-04-03 09:53 发表评论

poj 1024 Tester Program

lzmagic — Thu, 19 Mar 2009 00:59:00 GMT

/**
* (1)求各点到源点的最小步数（BFS）
* (2)求各点到终点的最小步数（BFS）
* (3)如果点不是给定路径上的点，那么：该点到源点的最小步数＋该点到终点的最小步数<给定路径的步数，否则给定路径不是唯一最短的
* (4)如果两相邻点a、b之间存在墙，那么：a到源点的最小步数＋1＋b到终点的最小步数<=给定路径的步数
*                              或者 a到终点的最小步数＋1＋b到源点的最小步数<=给定路径的步数，否则墙多余
* (5)如果存在点不可达，说明存在墙将该点封闭起来，可以证明墙至少有一块多余
*/
#include <iostream>
#include <string>
#include <queue>
using namespace std;

struct Grid
{
    bool inpath;    // 是否是路径方格
    bool uwal;      // 是否有上墙
    bool rwal;      // 是否有右墙
    int scnt;       // 到源点步数
    int dcnt;       // 到终点步数
};

int main(int argc, char** argv)
{
    bool ok;
    int w, h, cnt, steps;   // 1 <= w, h <= 100
    string path;
    Grid grid[100][100];
    queue<pair<int, int> > q;

    int t, x, y, desx, desy, x2, y2, i;
    for (cin >> t; t > 0; --t)
    {
        // 初始化数据
        cin >> w >> h;
        for (y = 0; y < h; ++y)
            for (x = 0; x < w; ++x)
            {
                grid[y][x].inpath = false;
                grid[y][x].uwal = false;
                grid[y][x].rwal = false;
                grid[y][x].scnt = -1;
                grid[y][x].dcnt = -1;
            }
        cin >> path;
        x = 0, y = 0;
        grid[0][0].inpath = true;
        steps = path.size();
        for (i = 0; i < steps; ++i)
        {
            switch(path[i])
            {
                case 'U': ++y; break;
                case 'D': --y; break;
                case 'L': --x; break;
                case 'R': ++x; break;
            }
            grid[y][x].inpath = true;
        }
        desx = x, desy = y;
        cin >> cnt;
        for (i = 0; i < cnt; ++i)
        {
            cin >> x >> y >> x2 >> y2;
            if (x == x2)
                if (y + 1 == y2) grid[y][x].uwal = true;
                else grid[y2][x].uwal = true;
            else
                if (x + 1 == x2) grid[y][x].rwal = true;
                else grid[y][x2].rwal = true;
        }

        // 求各点到源点的最小步数（BFS）
        q.push(make_pair(0, 0));
        grid[0][0].scnt = 0;
        while (!q.empty())
        {
            y = q.front().first, x = q.front().second;
            if (y < h - 1 && grid[y][x].uwal == false && grid[y + 1][x].scnt == -1)
            {
                grid[y + 1][x].scnt = grid[y][x].scnt + 1;
                q.push(make_pair(y + 1, x));
            }
            if (0 < y && grid[y - 1][x].uwal == false && grid[y - 1][x].scnt == -1)
            {
                grid[y - 1][x].scnt = grid[y][x].scnt + 1;
                q.push(make_pair(y - 1, x));
            }
            if (0 < x && grid[y][x - 1].rwal == false && grid[y][x - 1].scnt == -1)
            {
                grid[y][x - 1].scnt = grid[y][x].scnt + 1;
                q.push(make_pair(y, x - 1));
            }
            if (x < w - 1 && grid[y][x].rwal == false && grid[y][x + 1].scnt == -1)
            {
                grid[y][x + 1].scnt = grid[y][x].scnt + 1;
                q.push(make_pair(y, x + 1));
            }
            q.pop();
        }

        // 求各点到终点的最小步数（BFS）
        q.push(make_pair(desy, desx));
        grid[desy][desx].dcnt = 0;
        while (!q.empty())
        {
            y = q.front().first, x = q.front().second;
            if (y < h - 1 && grid[y][x].uwal == false && grid[y + 1][x].dcnt == -1)
            {
                grid[y + 1][x].dcnt = grid[y][x].dcnt + 1;
                q.push(make_pair(y + 1, x));
            }
            if (0 < y && grid[y - 1][x].uwal == false && grid[y - 1][x].dcnt == -1)
            {
                grid[y - 1][x].dcnt = grid[y][x].dcnt + 1;
                q.push(make_pair(y - 1, x));
            }
            if (0 < x && grid[y][x - 1].rwal == false && grid[y][x - 1].dcnt == -1)
            {
                grid[y][x - 1].dcnt = grid[y][x].dcnt + 1;
                q.push(make_pair(y, x - 1));
            }
            if (x < w - 1 && grid[y][x].rwal == false && grid[y][x + 1].dcnt == -1)
            {
                grid[y][x + 1].dcnt = grid[y][x].dcnt + 1;
                q.push(make_pair(y, x + 1));
            }
            q.pop();
        }

        // 判断路径是否唯一最短，以及墙是否多余
        ok = true;
        for (y = 0; y < h && ok; ++y)
            for (x = 0; x < w && ok; ++x)
            {
                if (grid[y][x].scnt == -1 || grid[y][x].dcnt == -1)
                    ok = false;     // 是否有封闭区域
                if (y < h - 1 && grid[y][x].uwal
                        && grid[y][x].scnt + grid[y + 1][x].dcnt + 1 > steps
                        && grid[y][x].dcnt + grid[y + 1][x].scnt + 1 > steps)
                    ok = false;     // 是否上墙多余
                if (x < w - 1 && grid[y][x].rwal
                        && grid[y][x].scnt + grid[y][x + 1].dcnt + 1 > steps
                        && grid[y][x].dcnt + grid[y][x + 1].scnt + 1 > steps)
                    ok = false;     // 是否右墙多余
                if (!grid[y][x].inpath && grid[y][x].scnt + grid[y][x].dcnt <= steps)
                    ok = false;     // 是否存在更短路径或另一最短路径
            }
        if(ok) cout << "CORRECT" << endl;
        else cout << "INCORRECT" << endl;
    }

    return 0;
}

lzmagic 2009-03-19 08:59 发表评论

poj 1022 Packing Unit 4D Cubes

lzmagic — Wed, 18 Mar 2009 04:04:00 GMT

/**
* FloodFill算法，深度遍历搜索。
*/
#include <iostream>
#include <map>
using namespace std;

struct Cube
{
    bool used;          // 是否已经使用
    int cood[4];        // 坐标
    int neighbor[4][2]; // 相邻标识号
};

void FloodFill(int row, int cnt, Cube *cube, int maxmin[4][2])
{
    if (cube[row].used == false)
    {
        cube[row].used = true;

        int i, j, k, row2;
        for (i = 0; i < 4; ++i)
            for (j = 0; j < 2; ++j)
                if (cube[row].neighbor[i][j] != -1 && cube[cube[row].neighbor[i][j]].used == false)
                {
                    row2 = cube[row].neighbor[i][j];
                    for (k = 0; k < 4; ++k)
                        cube[row2].cood[k] = cube[row].cood[k];
                    if (j == 0)
                    {
                        ++cube[row2].cood[i];
                        if (maxmin[i][0] < cube[row2].cood[i])
                            maxmin[i][0] = cube[row2].cood[i];
                    }
                    else
                    {
                        --cube[row2].cood[i];
                        if (maxmin[i][1] > cube[row2].cood[i])
                            maxmin[i][1] = cube[row2].cood[i];
                    }
                    FloodFill(row2, cnt, cube, maxmin);
                }
    }
}

int main(int argc, char** argv) {

    bool ok;
    int cnt;    // 1 <= cnt <= 100
    int maxmin[4][2];
    int minv;
    Cube cube[100];
    map <int, int> idmap;

    int t, i, j, k, id;
    for (cin >> t; t > 0; --t)
    {
        // 输入数据
        cin >> cnt;
        idmap.clear();
        for (i = 0; i < cnt; ++i)
        {
            cube[i].used = false;
            cin >> id;
            idmap[id] = i;
            for (j = 0; j < 4; ++j)
                for (k = 0; k < 2; ++k)
                    cin >> cube[i].neighbor[j][k];
        }

        // 标识号改为对应的行号
        for (i = 0; i < cnt; ++i)
            for (j = 0; j < 4; ++j)
                for (k = 0; k < 2; ++k)
                    cube[i].neighbor[j][k] = (cube[i].neighbor[j][k] == 0) ? -1 : idmap[cube[i].neighbor[j][k]];

        // 判断是否对称
        ok = true;
        for (i = 0; i < cnt && ok; ++i)
            for (j = 0; j < 4 && ok; ++j)
                for (k = 0; k < 2 && ok; ++k)
                    if (cube[i].neighbor[j][k] != -1 && cube[cube[i].neighbor[j][k]].neighbor[j][1 - k] != i)
                        ok = false;
        if (!ok)
        {
            cout << "Inconsistent" << endl;
            continue;
        }

        // Flood Fill 算法 (种子染色法)
        for (i = 0; i < 4; ++i) cube[i].cood[i] = 0;
        for (i = 0; i < 4; ++i) maxmin[i][0] = maxmin[i][1] = 0;
        FloodFill(0, cnt, cube, maxmin);

        // 判断是否连通
        ok = true;
        for (i = 0; i < cnt && ok; ++i)
            if (cube[i].used == false)
                ok = false;
        if (!ok)
        {
            cout << "Inconsistent" << endl;
            continue;
        }

        // 计算最小体积
        minv = 1;
        for (i = 0; i < 4; ++i)
            minv *= maxmin[i][0] - maxmin[i][1] + 1;
        cout << minv << endl;
    }
    return 0;
}

测试数据：
Input:
6
9
1 2 3 4 5 6 7 8 9
2 0 1 0 0 0 0 0 0
3 1 0 0 0 0 0 0 0
4 0 0 0 1 0 0 0 0
5 0 0 1 0 0 0 0 0
6 0 0 0 0 0 1 0 0
7 0 0 0 0 1 0 0 0
8 0 0 0 0 0 0 0 1
9 0 0 0 0 0 0 1 0
2
3 0 0 1 0 0 0 0 0
1 0 0 3 0 0 0 0 0
4
1 2 0 0 0 0 0 0 0
2 0 1 0 0 0 0 0 0
3 0 0 4 0 0 0 0 0
4 0 0 0 3 0 0 0 0
5
101 2 0 0 0 0 0 0 0
2 0 101 321 0 0 0 0 0
321 4 0 0 2 0 0 0 0
4 5 321 0 0 0 0 0 0
5 0 4 0 0 0 0 0 0
1
10 0 0 0 0 0 0 0 0
4
1 0 2 4 0 0 0 0 0
2 1 0 3 0 0 0 0 0
3 4 0 0 2 0 0 0 0
4 0 3 0 1 0 0 0 0

Output:
81
Inconsistent
Inconsistent
8
1
4

lzmagic 2009-03-18 12:04 发表评论

加减乘除24

lzmagic — Tue, 21 Oct 2008 00:13:00 GMT

摘要: 1/**//** 2 * 程序：加减乘除24 3 * 输入：四个1到13整数（输入四个0结束） 1/**//** 2 * 程序：加减乘除24 ... 阅读全文

lzmagic 2008-10-21 08:13 发表评论