题解

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
    @ 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
上传者