最小割

51Nod 1499 图

Posted on

emmmmmmm不错的的最小割吧
唯一一个不是很好的点就是实在是太容易想到是最小割了,但是没想到具体的建图方法。

题意:
有n个点,m条边,要你分成两个集合,使得两个集合的导出子图各自权值和的和最大。
两个导出子图中,可选择其中一个,若导出子图中存在有两个点 (i,j) 相连,则该导出子图权值增加 $| i-j |$ 。同时另一个导出子图则相反,只有存在两个点没有边相连,才会增加权值。

思路:
题目的主要目的就是将点集分成两部分,这很容易想到二分图染色,但这是不现实的,因为这是一个最值问题,不存在必然关系。
而跟二分图相关的只有网络流了,将图分为两半是割的概念,当然只存在最小割,正面去想的话,就是总权值和-最小割。

然后……思路就断了,找不到有效的建图方法。

可以先这么想,我们假定与源点相连的点集为相连增加权值的集合,并称之为,与汇点相连的点集则相反,称之为汇点集。
那么我们先将每个点都与源点相连,其容量为将该点加入源点集所能增加的权值。
再将这个点与汇点相连,其容量为将该点加入汇点集所能增加的权值。

此时直接跑最小割是不对的,因为这些点并不是独立的。

其实只要再将任意两个点都连边就可以了。

啊,顺便发现一个,换一种无向图建边,速度快了一倍,因为边几乎少了一半

AC Code

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

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e3 + 5;
const int maxm = 5e6 + 5;
const int inf = 0x3f3f3f3f;

int src, des, idx;
int cur[maxn], level[maxn], head[maxn];

struct node {
    int to, next;
    int cap;
    node() {}
    node(int _to, int _next, int _cap) { to = _to, next = _next, cap = _cap; }
} edges[maxm << 1];

queue<int> que;

void addEdge(int u, int v, int c, int rc = 0)
{
    edges[idx] = node(v, head[u], c);
    head[u] = idx++;
    edges[idx] = node(u, head[v], rc);//无向边建边小技巧
    head[v] = idx++;
}

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

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

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

void init(int s, int d)
{
    memset(head, -1, sizeof head);
    idx = 0;
    src = s, des = d;
}

bool g[maxn][maxn];
int s[maxn], t[maxn];

inline void scan_d(int& num)
{
    char in;
    in = getchar();
    while (in != '-' && (in < '0' || in > '9'))
        in = getchar();
    num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') {
        num *= 10, num += in - '0';
    }
}

int main()
{
    int n, m, u, v, tmp;
    scan_d(n), scan_d(m);
    init(0, n + 1);
    while (m--) {
        scan_d(u), scan_d(v);
        g[u][v] = g[v][u] = true;
    }
    range(i, 1, n) range(j, i + 1, n)
    {
        tmp = j - i;
        if (g[i][j])
            s[i] += tmp, s[j] += tmp;
        else
            t[i] += tmp, t[j] += tmp;
        addEdge(i, j, tmp, tmp);
    }
    int ans = 0;
    range(i, 1, n) addEdge(src, i, s[i]), addEdge(i, des, t[i]);
    range(i, 1, n) ans += (1 + n - i) * (n - i) / 2;
    printf("%d\n", ans - dinic(n) / 2); //因为与源点汇点相连的点增加了一倍权值
    return 0;
}
强联通分量

CodeForces 864F Cities Excursions

Posted on

对Tarjan的算法理解有点要求的题,之前看了一下思路,敲了一下结果没过,照着博客改动了一下但并没有搞懂,今天补上。

题意:
给你一个有向图,若干询问,询问为从 s 到 t 的最小字典序路径中,第 k 个点是哪个点。

思路:
首先询问很多,有$4\times10^5$个询问,直接一个一个找肯定是不行的。
但是值得注意的是,点数比较少,只有$3000$个,假如我们固定起点,遍历全图来获得路径,在遍历的同时,对每一个点来记录答案。理想复杂度为$O(N^2)$,时间上满足条件。

一个问题是如何保证字典序最小,emmmm
用vector记录整张图,对于每个点的边进行排序,因为每个点访问一次,解决之。

这题还有一个合理的大坑,如果在遍历的时候,在之前已经出现了一个环,那么之后的所有点就都不会被访问。
当然你不能在找到一个环后,后面的点就不再遍历,这样会使最小字典树发生变化,会导致错误答案。
好题啊。

以上。

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 3e3 + 5;
const int maxq = 4e5 + 5;

struct Item {
    int u, v, q, id;
    bool operator<(const Item& item) const { return u < item.u; }
} items[maxq];

int dfn[maxn], low[maxn], vis[maxn], vtm;
int path[maxn], ans[maxq];
vector<int> G[maxn];
vector<Item> qary[maxn];

void tarjan(int u, int dep, bool cant)
{
    path[dep] = u;
    low[u] = dfn[u] = ++vtm;
    vis[u] = 1;
    int sz = qary[u].size();
    if (!cant)
        each(i, sz)
        {
            Item& item = qary[u][i];
            if (item.q <= dep)
                ans[item.id] = path[item.q];
        }
    sz = G[u].size();
    each(i, sz)
    {
        int v = G[u][i];
        if (!vis[v]) {
            tarjan(v, dep + 1, cant | (low[u] < dfn[u]));
            low[u] = min(low[u], low[v]);
            cant |= (low[v] < dfn[v]);
        } else if (vis[v] == 1)
            low[u] = min(low[u], dfn[v]);
    }
    vis[u] = 2;
}

int main()
{
    int n, m, q, u, v;
    scanf("%d %d %d", &n, &m, &q);
    each(i, m)
    {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
    }
    range(i, 1, n) sort(G[i].begin(), G[i].end());
    each(i, q)
    {
        Item& item = items[i];
        scanf("%d %d %d", &item.u, &item.v, &item.q);
        item.id = i;
    }
    sort(items, items + q);
    fill(ans, -1);
    each(i, q)
    {
        Item& item = items[i];
        qary[item.v].push_back(item);
        if (i == q - 1 || item.u != items[i + 1].u) {
            vtm = 0, fill(vis, 0);
            tarjan(item.u, 1, false);
            range(j, 1, n) qary[j].clear();
        }
    }
    each(i, q) printf("%d\n", ans[i]);
    return 0;
}
宅技术

OwnCloud 作为图床的简易使用方法

Posted on

今天因为薛昊买VPS了,赚点访问量简单写一下吧。

OwnCloud是开源私有云软件,功能强大,作为图床只是其一个小用法。
我的ACM模板和一些很重要的文件都在上面,在本地与云服务器中都有保存。

DigtalOcean的官方论坛上的关于安装OwnCloud的文章不错,是安装教程的不二选择。传送门

以下是标题相关正文,假设你已经搭建完成

  1. 新建一个文件夹,并对其分享。这个文件夹作为我们的图床目录。
  2. 在浏览器中打开分享目录。右击图片,点击复制下载链接。

2017-10-28 17:44:53 星期六 更新,mmp,owncloud改了???
换一个方法,得到分享目录地址后,在后面加上download?path=%2F&files=image.png
即可。
files=后面的是图片文件名

该链接就是可以用markdown,html或者其他显示出来的链接。

就这么简单。
但是在不安装插件的情况下也只有这么一种操作选择。其他都无效。

当然这个方法是有缺点的:
显然其他人如果知道了你的服务器ip,那么你图床上的所有图片都会以一个目录的形式所展现出来。

But who cares,一般会玩的人都知道隐藏ip,而且只要不放一些违背社会主义核心价值管并且不会涉及一些隐私的图片,这个缺点可以忽略不计。

心情随笔

悲伤的故事

Posted on

今天老友跟女神走一路,赶着上课的时候老友喊了我一声。
我回头看了一眼,因为要迟到了就没回应。
老友后来跟我说,女神问她

“你刚刚喊的人是谁啊”

完。

区间DP

POJ 1991 Turning in Homework

Posted on

/doge薛昊老是偷我题做,最近我也就拿他博客上的题来练练手。其中这道题真的什么思路都没有,这个区间DP的套路我还真没碰到过。

这是一个大区间推小区间的套路。

题意:
小明要在某层楼的各个老师那里交一大堆作业,但是小明来早了,老师还没上班,他站在这层楼的最左边,告诉你每个老师的上班时间,最后要在某个给定位置下楼,问最少时间。

思路:
shit,完全是看博客,看代码敲的。
一个比较困难的点在于给定离开地点,算了,不装了,就算取消这个条件我也写不来……
明确可以用dp求解,首先按照位置优先开门顺序次优的顺序排序,设三维数组 $dp[l][r][k]$。
当 $k=0$ 时,表示只有 $(l,r] $ 区间内的作业没有交。
而 $k=1$ 时,表示只有 $[l,r) $ 区间内的作业没有交。
而我们的其实状态$dp[1][n][0/1]$是已知的,我们完全可以由此不断向内挤压求出小区间的结果。
当 $l=r$ 时,则所有作业交完,且停在 $l$ 点。

AC Code

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

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
int dp[maxn][maxn][2];
pii point[maxn];

int getDis(int d, int s) { return point[d].first - point[s].first; }

int main()
{
    int n, h, b;
    scanf("%d %d %d", &n, &h, &b);
    range(i, 1, n) scanf("%d %d", &point[i].first, &point[i].second);
    sort(point + 1, point + 1 + n);
    fill(dp, 0x3f);
    dp[1][n][0] = max(point[1].first, point[1].second);
    dp[1][n][1] = max(point[n].first, point[n].second);
    rrange(len, 1, n - 1) range(l, 1, n + 1 - len)
    {
        int r = l + len - 1;
        if (l > 1) {
            dp[l][r][0] = min(dp[l][r][0], dp[l - 1][r][0] + getDis(l, l - 1));
            dp[l][r][1] = min(dp[l][r][1], dp[l - 1][r][0] + getDis(r, l - 1));
        }
        if (r < n) {
            dp[l][r][0] = min(dp[l][r][0], dp[l][r + 1][1] + getDis(r + 1, l));
            dp[l][r][1] = min(dp[l][r][1], dp[l][r + 1][1] + getDis(r + 1, r));
        }
        dp[l][r][0] = max(dp[l][r][0], point[l].second);
        dp[l][r][1] = max(dp[l][r][1], point[r].second);
    }
    int ans = inf;
    range(i,1,n) ans = min(ans,dp[i][i][0]+abs(b-point[i].first));
    printf("%d\n",ans);
    return 0;
}