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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

最小割

HihoCoder 1252 Kejin Game

网络流建图神题!!! 同时也是2015年北京现场赛的金牌题,虽然我不可 Read more…

最小割

HDU 6126 Give out candies

例行废话 哇~,惊了,多校里面第一次出现网络流的题目。然而我并没有时间 Read more…

最小割

ZOJ 3475 The Great Wall I

最小割建图好题!! 昨天比赛的最小割,当时没看出来,实际上需要建图转化 Read more…