【BZOJ 1061】【Vijos 1825】【NOI 2008】志愿者招募

发布时间:2017-3-24 0:34:53 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"【BZOJ 1061】【Vijos 1825】【NOI 2008】志愿者招募 ",主要涉及到【BZOJ 1061】【Vijos 1825】【NOI 2008】志愿者招募 方面的内容,对于【BZOJ 1061】【Vijos 1825】【NOI 2008】志愿者招募 感兴趣的同学可以参考一下。

http://www.lydsy.com/JudgeOnline/problem.php?id=1061
https://vijos.org/p/1825
直接上姜爷论文。。。



#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long ll;const int N = 1013;const int M = 40003;const int inf = 0x7fffffff;struct node {int nxt, to, c, w, from;} E[M];int cnt = 1, point[N << 1];void ins(int u, int v, int c, int w) {    E[++cnt] = (node) {point[u], v, c, w, u}; point[u] = cnt;    E[++cnt] = (node) {point[v], u, 0, -w, v}; point[v] = cnt;}bool inq[N];int dist[N], pre[N], q[N];bool spfa(int s, int t) {    for (int i = s; i <= t; ++i) dist[i] = inf, pre[i] = 0;    int u, v, tt, head = 0, tail = 1; q[1] = s; inq[s] = true; dist[s] = 0;    while (head != tail) {        ++head; if (head == N) head = 0;        u = q[head]; inq[u] = false;        for (int i = point[u]; i; i = E[i].nxt)            if (E[i].c && dist[v = E[i].to] > (tt = dist[u] + E[i].w)) {                dist[v] = tt; pre[v] = i;                if (!inq[v]) {                    inq[v] = true;                    ++tail; if (tail == N) tail = 0;                    q[tail] = v;                }            }    }    return dist[t] != inf;}ll MCMF(int s, int t) {    ll ret = 0;    while (spfa(s, t)) {        int f = inf;        for (int u = t; u != s; u = E[pre[u]].from) f = min(f, E[pre[u]].c);        for (int u = t; u != s; u = E[pre[u]].from) E[pre[u]].c -= f, E[pre[u] ^ 1].c += f;        ret += f * dist[t];    }    return ret;}int n, m, s, t, c, S, T, a[N];int main() {    scanf("%d%d", &n, &m);    S = 0; T = n + 2;    for (int i = 1; i <= n; ++i) scanf("%d", a + i);    for (int i = 0; i <= n; ++i) {        int num = a[i + 1] - a[i];        if (num < 0) ins(i + 1, T, -num, 0);        if (num > 0) ins(S, i + 1, num, 0);    }    for (int i = 1; i <= n; ++i) ins(i + 1, i, inf, 0);    for (int i = 1; i <= m; ++i) {        scanf("%d%d%d", &s, &t, &c);        ins(s, t + 1, inf, c);    }        printf("%lld\n", MCMF(S, T));    return 0;

上一篇:iOS:根据日志去定位网络请求发生的错误是由于服务端造成的,还是客户端造成的?
下一篇:linux的5个查找命令_转

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款