最大流

SPOJ 962 IM – Intergalactic Map

Posted on

一眼题,但是有个很坑的地方,我看了题目没注意。
就是输入数据会有无效输入……结果贡献了3发wa,还不断尝试开大数组……

传送门

题意:
给你一张无向图,让你从1点出发,经过2点,最后到3点,能否实现。每个点只能去一次。

思路:
肯定是拆点啦,容量设置成1即可。再从2开始跑,看流量能否为2。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>

using namespace std;
const int maxn = 66500;
const int inf = 0x3f3f3f3f;

int n, m, st, en, idx;
int level[maxn], cur[maxn];
int head[maxn];

struct node {
    int to;
    int nxt;
    int flow;
} edges[551000];

queue<int> que;

inline void addEdge(int u, int v, int flow)
{
    edges[idx].to = v;
    edges[idx].flow = flow;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

bool bfs()
{
    while (!que.empty())
        que.pop();
    memset(level, -1, sizeof level);
    que.push(st);
    level[st] = 0;
    int u;
    while (!que.empty()) {
        u = que.front();
        que.pop();
        for (int id = head[u]; ~id; id = edges[id].nxt) {
            int v = edges[id].to;
            if (edges[id].flow && level[v] == -1) {
                level[v] = level[u] + 1;
                que.push(v);
            }
        }
    }
    return level[en] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == en)
        return low;
    for (int& id = cur[u]; ~id; id = edges[id].nxt) {
        int v = edges[id].to;
        if (edges[id].flow && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, edges[id].flow)))) {
            edges[id].flow -= cflow;
            edges[id ^ 1].flow += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic()
{
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = 0; i <= 2 * n; i++)
            cur[i] = head[i];
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

int main()
{
    int T, u, v;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        memset(head, -1, sizeof head);
        idx = 0;
        for (int i = 1; i <= n; i++) {
            addEdge(i, i + n, 1);
            addEdge(i + n, i, 0);
        }
        while (m--) {
            scanf("%d %d", &u, &v);
            if (u < 1 || v < 1 || u > n || v > n)
                continue;
            addEdge(u + n, v, 1);
            addEdge(v + n, u, 1);
        }
        st = 2 + n, en = 2 * n + 1;
        addEdge(1 + n, en, 1);
        addEdge(en, 1 + n, 0);
        addEdge(3 + n, en, 1);
        addEdge(en, 3 + n, 0);
        if (dinic() == 2)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}
最短路

HDU 4725 The Shortest Path in Nya Graph

Posted on

貌似是卡spfa的,但薛昊说slf优化一下也可以过
个人感觉写的非常崩溃……用数组实现队列的时候是WA,stl实现就是tle,我觉得这很可能是空间上的问题。因为最近数组大小开错不停wa不停tle的情况太多了……
看很多题解都是dijkstra实现的。改了一下直接A了

题意:
美团初赛城市群的原题……上次没写出来,碰到原题真的是内心崩溃。
简单说,在一张图的基础上,每个节点都会属于一个 “ 层 ” ,每个相邻的 “ 层 ” 中的节点都相互可达,问 1 到 n 的最短距离。

思路:
对 “ 层 ” 建立源点与汇点,对于每个层里面的每个点,源点到点 ,点到汇点的距离各为 0 。再对 “ 层 ” 之间建边,点之间建边跑最短路即可。

AC Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;

int dis[maxn], head[maxn];
bool vis[maxn];
int n, m, c, idx;

struct node {
    int to;
    int nxt;
    int weight;
} edges[maxn];

struct qnode {
    int to;
    int weight;
    qnode(int _to = 0, int _weight = 0)
        : to(_to)
        , weight(_weight)
    {
    }
    bool operator<(const qnode& a) const
    {
        return weight > a.weight;
    }
};

priority_queue<qnode> que;

void Dijkstra(int n, int start) 
{
    memset(vis, false, sizeof(vis));
    for (int i = 1; i <=3* n; i++)
        dis[i] = inf;
    while (!que.empty())
        que.pop();
    dis[start] = 0;
    que.push(qnode(start, 0));
    qnode tmp;
    while (!que.empty()) {
        tmp = que.top();
        que.pop();
        int u = tmp.to;
        if (vis[u])
            continue;
        vis[u] = true;
        for (int id = head[u]; ~id; id = edges[id].nxt) {
            int v = edges[id].to;
            int cost = edges[id].weight;
            if (!vis[v] && dis[v] > dis[u] + cost) {
                dis[v] = dis[u] + cost;
                que.push(qnode(v, dis[v]));
            }
        }
    }
    printf("%d\n", dis[n] == inf ? -1 : dis[n]);
}

inline void addEdge(int u, int v, int w)
{
    edges[idx].to = v;
    edges[idx].weight = w;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

int main()
{
    int T, u, v, w, layer;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d %d %d", &n, &m, &c);
        memset(head, -1, sizeof head);
        idx = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &layer);
            addEdge(n + layer * 2 - 1, i, 0);
            addEdge(i, n + 2 * layer, 0);
        }
        for (int i = 1; i < n; i++) {
            addEdge(n + 2 * i, n + 2 * i + 1, c);
            addEdge(n + 2 * i + 2, n + 2 * i - 1, c);
        }
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &u, &v, &w);
            addEdge(u, v, w);
            addEdge(v, u, w);
        }
        printf("Case #%d: ", cas);
        Dijkstra(n,1);
    }
    return 0;
}
IDA*

POJ 2286 The Rotation Game

Posted on

康复计划 之 ida*

题意:

这种玩具要你操作最少次数且操作字典序最小,使得中间的8个数字相同。

思路:
迭代加深 启发式 搜索
估价函数采用 8 - 中间数字最多的数字数量
因为每次操作如果想达到最终结果,一次最多只能转化出一个,如 aaab ,一次转化出两个的话,中间那个必定不相同,可以自己在纸上试试。

这道题本身在深搜层数上并不会很大,ida * 的优势就体现了出来。

AC Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

vector<int> ans;
int ary[30], deep;
int center[] = { 7, 8, 9, 12, 13, 16, 17, 18 };
int ret[] = { 5, 4, 7, 6, 1, 0, 3, 2 };
int mat[][8] = {
    { 1, 3, 7, 12, 16, 21, 23 },
    { 2, 4, 9, 13, 18, 22, 24 },
    { 11, 10, 9, 8, 7, 6, 5 },
    { 20, 19, 18, 17, 16, 15, 14 },
    { 24, 22, 18, 13, 9, 4, 2 },
    { 23, 21, 16, 12, 7, 3, 1 },
    { 14, 15, 16, 17, 18, 19, 20 },
    { 5, 6, 7, 8, 9, 10, 11 }
};

bool isEnd()
{
    int tmp = ary[7];
    for (int i = 1; i < 8; i++)
        if (tmp != ary[center[i]])
            return false;
    return true;
}

void change(int dir)
{
    int tmp = ary[mat[dir][0]];
    for (int i = 0; i < 6; i++)
        ary[mat[dir][i]] = ary[mat[dir][i + 1]];
    ary[mat[dir][6]] = tmp;
}

int getH()
{
    int num[4] = { 0 };
    for (int i = 0; i < 8; i++)
        num[ary[center[i]]]++;
    return 8 - max(num[1], max(num[2], num[3]));
}

bool dfs(int now)
{
    if (now == deep)
        return isEnd();
    int h = getH();
    if (now + h > deep)
        return false;
    for (int i = 0; i < 8; i++) {
        change(i);
        ans.push_back(i);
        if (dfs(now + 1))
            return true;
        ans.pop_back();
        change(ret[i]);
    }
    return false;
}

int main()
{
    while (scanf("%d", &ary[1]) != EOF && ary[1]) {
        for (int i = 2; i <= 24; i++)
            scanf("%d", ary + i);
        ans.clear();
        if (isEnd()) {
            puts("No moves needed");
            printf("%d\n", ary[7]);
            continue;
        }
        deep = 1;
        while (dfs(0) == false)
            deep++;
        for (unsigned i = 0; i < ans.size(); i++)
            printf("%c", ans[i] + 'A');
        printf("\n%d\n", ary[7]);
    }
    return 0;
}
BFS

HDU 1043 Eight

Posted on

康复计划之搜索 1
因为有个小学弟在第二天就说ida * 看不懂,搞得我挺慌 我可以说我也不是很熟么

题意:
经典八数码

思路:
这里提供的是单向bfs + 打表思路,本来想复习ida * 但是不小心看到了kuangbin的思路,就写了一下。

简单说就是我从起始状态 123456780 开始对0进行bfs,通过康托展开的hash函数进行记录状态和路径。询问时对哈希值进行询问和查找。

实际上并没有用到康托展开的性质,只是通过2进制hash而已……

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>

using namespace std;
const int maxn = 400000;

int fac[] = { 0, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
string path[maxn];
bool vis[maxn];
int dx[] = { 0, -1, 0, 1 };
int dy[] = { -1, 0, 1, 0 };
char dir[] = "rdlu";

struct node {
    int s[9];
    int zero_pos;
    int hash;
    string path;
};

int cantor_hash(int s[])
{
    int res = 0;
    for (int i = 0; i < 9; i++) {
        int renum = 0;
        for (int j = i + 1; j < 9; j++)
            if (s[i] > s[j])
                renum++;
        res += (renum * fac[9 - i - 1]);
    }
    return res;
}

void init()
{
    memset(vis, false, sizeof vis);
    node cur, nxt;
    for (int i = 0; i < 8; i++)
        cur.s[i] = i + 1;
    cur.s[8] = 0;
    cur.zero_pos = 8;
    cur.hash = cantor_hash(cur.s);
    path[cur.hash] = "";
    vis[cur.hash] = true;
    queue<node> que;
    que.push(cur);
    while (!que.empty()) {
        cur = que.front();
        que.pop();
        int x = cur.zero_pos / 3;
        int y = cur.zero_pos % 3;
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx < 0 || xx > 2 || yy < 0 || yy > 2)
                continue;
            nxt = cur;
            nxt.zero_pos = xx * 3 + yy;
            nxt.s[cur.zero_pos] = nxt.s[nxt.zero_pos];
            nxt.s[nxt.zero_pos] = 0;
            nxt.hash = cantor_hash(nxt.s);
            if (!vis[nxt.hash]) {
                nxt.path = dir[i] + cur.path;
                path[nxt.hash] = nxt.path;
                que.push(nxt);
                vis[nxt.hash] = true;
            }
        }
    }
}

int main()
{
    init();
    node cur;
    char buf[2];
    while (scanf("%s", buf) != EOF) {
        if (buf[0] == 'x') {
            cur.zero_pos = 0;
            cur.s[0] = 0;
        } else
            cur.s[0] = buf[0] - '0';
        for (int i = 1; i < 9; i++) {
            scanf("%s", buf);
            if (buf[0] == 'x') {
                cur.zero_pos = i;
                cur.s[i] = 0;
            } else
                cur.s[i] = buf[0] - '0';
        }
        cur.hash = cantor_hash(cur.s);
        //cout << cur.hash << endl;
        if (vis[cur.hash])
            cout << path[cur.hash] << endl;
        else
            puts("unsolvable");
    }
    return 0;
}