/ Vijos / 题库 / 生命之泉 /

题解

32 条题解

  • 1
    @ 2017-07-12 15:53:10 
    #include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m,t;
vector<int> f;
vector<int> e;
vector<int> u;
vector<int> pre;
vector<int> vis;
vector<vector<int> > c;
vector<vector<int> > p;
vector<vector<int> > ce;
vector<vector<int> > cw;
deque<int> q;

void add_edge_1(int x,int y,int c_v,int p_v)
{
    cw[x].push_back(y);
    c[x].push_back(c_v);
    p[x].push_back(p_v);
    ce[y].push_back(cw[x].size()-1);
    cw[y].push_back(x);
    c[y].push_back(0);
    p[y].push_back(-p_v);
    ce[x].push_back(cw[y].size()-1);
}

int bfs_1(int s,int t,int *flow,int *cost)
{
    f.resize(0);
    f.resize(cw.size(),0);
    f[s]=oo_max;
    e.resize(0);
    e.resize(cw.size(),-1);
    u.resize(0);
    u.resize(cw.size(),oo_max);
    u[s]=0;
    pre.resize(0);
    pre.resize(cw.size(),-1);
    pre[s]=s;
    vis.resize(0);
    vis.resize(cw.size(),0);
    for (q.resize(0),vis[s]=1,q.push_back(s);(!q.empty());vis[q.front()]=0,q.pop_front())
    {
        int now=q.front();
        for (int i=0;i<cw[now].size();i++)
            if (c[now][i]&&u[now]+p[now][i]<u[cw[now][i]])
            {
                f[cw[now][i]]=min(c[now][i],f[now]);
                e[cw[now][i]]=i;
                u[cw[now][i]]=u[now]+p[now][i];
                pre[cw[now][i]]=now;
                if (vis[cw[now][i]]==0)
                    vis[cw[now][i]]=1,q.push_back(cw[now][i]);
            }
    }
    (*flow)=f[t];
    (*cost)=u[t];
    return (pre[t]!=-1);
}

void min_cost_max_flow_1(int s,int t,int *flow,int *cost)
{
    int temp_flow,temp_cost;
    while (bfs_1(s,t,&temp_flow,&temp_cost))
    {
        for (int i=t;i!=s;i=pre[i])
            c[pre[i]][e[i]]-=temp_flow,c[i][ce[pre[i]][e[i]]]+=temp_flow;
        (*flow)+=temp_flow;
        (*cost)+=temp_cost;
    }
}

int main()
{
    while (~scanf("%d%d%d",&t,&n,&m))
    {
        cw.resize(0);
        cw.resize(t+2);
        ce.resize(0);
        ce.resize(cw.size());
        c.resize(0);
        c.resize(cw.size());
        p.resize(0);
        p.resize(cw.size());
        for (int i=0;i<cw.size();i++)
        {
            cw[i].resize(0);
            ce[i].resize(0);
            c[i].resize(0);
            p[i].resize(0);
        }
        for (int i=0;i<cw.size()-1;i++)
            add_edge_1(i,i+1,m,0);
        for (int i=1;i<=n;i++)
        {
            int x,y,v;
            scanf("%d%d%d",&x,&y,&v);
            add_edge_1(x,y+1,1,-v);
        }
        int ans_flow=0,ans_cost=0;
        min_cost_max_flow_1(0,cw.size()-1,&ans_flow,&ans_cost);
        printf("%d\n",-ans_cost);
    }
}
  • 0
    @ 2017-01-03 21:15:41

    测试数据 #0: Accepted, time = 46 ms, mem = 760 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 760 KiB, score = 10
    测试数据 #2: Accepted, time = 46 ms, mem = 760 KiB, score = 10
    测试数据 #3: Accepted, time = 31 ms, mem = 760 KiB, score = 10
    测试数据 #4: Accepted, time = 31 ms, mem = 676 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 676 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 676 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 676 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 628 KiB, score = 10
    测试数据 #9: Accepted, time = 31 ms, mem = 676 KiB, score = 10
    Accepted, time = 230 ms, mem = 760 KiB, score = 100

    卡了很久才发现是BellmanFord部分写错了。。第一次提交的时候忘记去掉system("pause")了TLE。。。尴尬

    代码

    #include<iostream>
#include<iomanip>
#include<cstring>
#include<vector>
#include<sstream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<math.h>
#include<map>
#include<cctype>
#include<queue>
#include<functional>
#include<set>
#define Mem(a,b) memset((a),(b),sizeof((a)))
#define Sy system("pause")
const int maxn = 1100;
const int INF = 0x3f3f3f;
using namespace std;



struct MCMF{

    struct Edge
    {
        int from, to, cap, flow, cost;
        Edge(int a, int b, int c, int d, int e) :from(a), to(b), cap(c), flow(d), cost(e) {}
        Edge(){}
    };
    int n, m;
    vector<Edge> edges;
    vector<int> G[maxn];
    int inq[maxn], d[maxn], p[maxn], a[maxn];

    void init(int n){
        this->n = n;
        for (int i = 0; i < n; i += 1)G[i].clear(); edges.clear();
    }

    void AddEdge(int from, int to, int cap, int cost){
        edges.push_back(Edge(from, to, cap, 0, cost));
        edges.push_back(Edge(to, from, 0, 0, -cost));
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }

    bool BellmanFord(int s, int t, int & flow,int & cost){
        for (int i = 0; i < n; i += 1) d[i] = INF;
        memset(inq, 0, sizeof(inq));
        d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF;
        queue<int> Q;
        Q.push(s);
        while (!Q.empty())
        {
            int u = Q.front(); Q.pop();
            inq[u] = 0;
            for (int i = 0; i < G[u].size(); i += 1){
                Edge & e = edges[G[u][i]];
                if (e.cap > e.flow && d[e.to] > d[u] + e.cost){
                    d[e.to] = d[u] + e.cost;
                    p[e.to] = G[u][i];
                    a[e.to] = min(a[u], e.cap - e.flow);
                    if (!inq[e.to]){
                        Q.push(e.to); inq[e.to] = 1;
                    }
                }
            }
        }
        if (d[t] == INF) return false;
        flow += a[t];
        cost += d[t];

        for (int u = t; u != s; u = edges[p[u]].from){
            edges[p[u]].flow += a[t];
            edges[p[u] ^ 1].flow -= a[t];
        }
        return true;
    }

    int MinCostMaxFlow(int s, int t, int & cost){ 
        int flow = 0; cost = 0;
        while (BellmanFord(s, t, flow, cost));
        return flow;
    }
};

/* 

a到b时刻，a为源点S，b为汇点T

对每个i到i+1，连一条容量为k的边，然后对a到b时刻连一条容量为1费用为-c的边。

*/

int main(){
    int T, n, k;
    scanf("%d %d %d", &T, &n, &k);
    int a, b, c;
    int S = 0;
    MCMF D;
    D.init(T + 2);
    for (int i = 0; i <= T; i += 1){
        D.AddEdge(i, i + 1, k, 0);
    }
    for (int i = 0; i < n; i += 1){
        scanf("%d %d %d", &a, &b, &c);
        D.AddEdge(a, b+1, 1, -c);
    }
    int ans;
    D.MinCostMaxFlow(S, T+1, ans);
    printf("%d\n", -ans);

    //Sy;
    return 0;
}
  • 0
    @ 2014-05-29 14:14:33

    http://hi.baidu.com/macaulish64/item/647f4df06b34c6c01a111f1f

  • 0
    @ 2010-03-12 18:44:50

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    employee

  • 0
    @ 2009-11-07 13:26:45

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    该死的重边。。。

  • 0
    @ 2009-10-22 10:54:41

    把link[x]打成了c[link[x]]，调了n个小时

  • 0
    @ 2009-10-09 17:48:47

    。。。第200次提交。。纪念下

  • 0
    @ 2009-08-24 21:03:32

    把刚写好的employee改改就来交

  • 0
    @ 2009-07-23 13:12:03

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    第一次建图for i := s to e - 1...

    哎。小失误,应该是for i := s to e

  • 0
    @ 2009-07-22 22:50:32

    这邻接表搞得我好累，可恶的重边

  • 0
    @ 2009-07-22 14:48:22

    从邻接矩阵换乘邻接表。。结果就是这样。。。。。。。。。。

    for (int i = 0; i

  • 0
    @ 2009-07-22 13:23:49

    额 我连傻子增广都不会 。。。有重边。。。额 我太弱了 。邻接表学习ing

  • 0
    @ 2009-07-16 15:52:22

    用Spfa 傻子增广就好了。。。代码短。。。

  • 0
    @ 2009-06-29 19:38:47

    不会写有负边的最小费用最大流或者 没负边的最大费用流

    所以只好在建模上改造了..

    设第i个人是从 a[i] -> b[i] ,给你 c[i]的钱

    从时刻 0 到 t+1,这t+2个顶点, x->(x+1)连费用是 BIG,容量k的边

    a[i] -> b[i]+1 连 费用是 (b[i]-a[i]+1)*BIG - c[i],容量1的边

    求最小费用cost

    答案就是 (t+1)*MAXFLOW*BIG - cost. 其中易知 MAXFLOW=k.

    为了保证所有边全为非负,即对所有i,有(b[i]-a[i]+1)*BIG - c[i] >= 0

    读数据的时候把BIG的值确定下来就可以了

    为了保险用的 long long ,还好没溢出,不过这样就慢了好多.

  • 0
    @ 2009-06-29 00:00:24

    这题数据真弱 ……

    大家来做 PKU 3680 吧。。。与这道题目一样的

    我的题解 ：

    http://hi.baidu.com/winterlegend/blog/item/51690d08ce9559c63ac7636d.html

  • 0
    @ 2009-06-21 22:06:27

    有点郁闷套这种模型.....

    K段区间覆盖cai0715大牛空间里看到的..

    1.端点排序

    2.i->i+1连一条容量为K,费用为0的弧

    3.若原有C ij 则I->J一条容量为1费用为-CI,J的弧...(极WS..最大变最小)

    然后94 ZKW的神奇程序

    记到要先SPFA..~@

  • 0
    @ 2009-06-21 12:43:20

    线性规划+单纯形法的一大堆优化=AC

  • 0
    @ 2009-06-11 15:39:36

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    膜拜cai0715神牛的题解！此题不用拆点，只要将每个单位时间作为点，将点i和点i+1之间连一条边，容量为k，费用为0。然后对于每一组a、b、c，在a和b+1之间连一条容量为1，费用为c的边。做最大费用最大流即可。

  • 0
    @ 2009-05-15 16:10:29

    其实这个题和PKU 3680那个题是一摸一样的，只不过这个是闭区间，而那个是开区间。。。

    特殊处理下就行了。

    附PKU 3680的解题报告：

  • 0
    @ 2009-05-07 17:15:35

    线性规划+最大费用流。建议先看一下NOI2008的employee。

生命之泉

信息

ID
1525
难度
6
分类
图结构 | 网络流 点击显示
标签
(无)
递交数
526
已通过
154
通过率
29%
被复制
2
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1