33 条题解

  • 2
    @ 2017-07-13 17:19:47
    #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,a,b,cn,ca,cb;
    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_flow*temp_cost);
        }
    }
    
    int main()
    {
        while (~scanf("%d%d%d%d%d%d",&n,&a,&b,&cn,&ca,&cb))
        {
            cw.resize(0);
            cw.resize(2*n+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=1;i<=n;i++)
            {
                int x;
                scanf("%d",&x);
                add_edge_1(0,i,x,0);
                add_edge_1(i+n,cw.size()-1,x,0);
                add_edge_1(0,i+n,oo_max,cn);
                if (i+1<=n)
                    add_edge_1(i,i+1,oo_max,0);
                if (i+a+1<=n)
                    add_edge_1(i,i+n+a+1,oo_max,ca);
                if (i+b+1<=n)
                    add_edge_1(i,i+n+b+1,oo_max,cb);
            }
            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);
        }
    }
    
  • 2
    @ 2009-09-18 17:40:01

    额...奇怪了...

    (1) s-> (1,2,...n)连一条容量为inf,费用为f的边;

    (2) s->1 连一条容量为inf,费用为f的边,在连i->i+1容量为inf,费用为0的边.

    这2种建图有区别吗?不明白...(1)WA,(2)Ac

  • 1
    @ 2009-07-08 10:21:06

    最小费用最大流:

    设有顶点S,T,每天有顶点 G[i], 附加每天的往外供应的顶点 U[i]

    S->G[1],容量INF,费用 f

    G[i]->G,容量INF,费用0

    G[i]->T,容量为当天需求量,费用0

    S->U[i],容量为当天需求量,费用0

    U[i]->G,容量INF,费用fa

    U[i]->G,容量INF,费用fb

  • 0
    @ 2017-01-04 00:03:53

    测试数据 #0: Accepted, time = 0 ms, mem = 588 KiB, score = 20
    测试数据 #1: Accepted, time = 0 ms, mem = 584 KiB, score = 20
    测试数据 #2: Accepted, time = 0 ms, mem = 676 KiB, score = 20
    测试数据 #3: Accepted, time = 0 ms, mem = 676 KiB, score = 20
    测试数据 #4: Accepted, time = 15 ms, mem = 672 KiB, score = 20
    Accepted, time = 15 ms, mem = 676 KiB, score = 100
    代码

    第一次只有40分。。看题解才知道和原题不一样,这个构图上有一点点区别。。
    原题是需要a天洗完时,第i+a天就能用,但这个是i+a+1天,没差多少。。
    构图是用二分图感觉好理解一点。。还是感觉有点不能理解为什么可以这么去想,还是要加油

    #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] * a[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;
        }
    };
    
    /* 
    
    S: 0  DLi:[1,n]  DRi:[n+1,2n] T:2n+1
    
    */
    
    int main(){
        int n, a, b, f, fa, fb,tmp;
        scanf("%d %d %d %d %d %d", &n, &a, &b, &f, &fa, &fb);
        int S = 0, T = 2 * n + 1;
        MCMF D; D.init(2 * n + 2);
        for (int i = 1; i <= n; i += 1){
            scanf("%d", &tmp);
            D.AddEdge(S, i, tmp, 0);
            D.AddEdge(i + n, T, tmp, 0);
            D.AddEdge(S, i + n, INF, f);
            if (i + 1 <= n) D.AddEdge(i, i + 1, INF, 0);
            if (i + a + 1<= n) D.AddEdge(i, i + n + a + 1, INF, fa);
            if (i + b + 1 <= n) D.AddEdge(i, i + n + b + 1, INF, fb);
        }
        int ans;
        D.MinCostMaxFlow(S, T, ans);
        printf("%d\n", ans);
    
        //Sy;
        return 0;
    }
    
  • 0
    @ 2013-12-14 10:58:55

    厉害

  • 0
    @ 2013-08-23 19:03:24

    直接拿BZOJ超时的代码过来,居然还A了。。。。
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 504 KiB, score = 20
    测试数据 #1: Accepted, time = 0 ms, mem = 492 KiB, score = 20
    测试数据 #2: Accepted, time = 31 ms, mem = 1376 KiB, score = 20
    测试数据 #3: Accepted, time = 31 ms, mem = 1412 KiB, score = 20
    测试数据 #4: Accepted, time = 46 ms, mem = 1176 KiB, score = 20
    Accepted, time = 108 ms, mem = 1412 KiB, score = 100
    #include <cstdio>
    #include <algorithm>
    #include <queue>
    #include <cstring>

    using namespace std;

    #define MAXN 2010

    struct node {
    node *next,*other;
    int t,f,c;
    };

    node *head[MAXN];

    int n,a,b,fa,fb,f;

    void INSERT(int s,int t,int f,int c){
    node *p=new(node);
    (*p).t=t;
    (*p).f=f;
    (*p).c=c;
    (*p).next=head[s];
    head[s]=p;
    }

    int S,T;

    int minc[MAXN],minf[MAXN],su[MAXN];
    bool flag[MAXN];
    node* d[MAXN];

    struct cmp{
    bool operator()(int x,int y){
    return minc[x]>minc[y];
    }
    };

    priority_queue<int,vector<int>,cmp>q;
    /*
    void OUT(){
    for (int i=0;i++<T;){
    printf("%d:\n",i);
    node *p=head[i];
    while (p!=NULL){
    // if ((*p).f){
    printf("%d %d %d\n",(*p).t,(*p).f,(*p).c);
    // }
    p=(*p).next;
    }
    printf("\n\n");
    }
    }
    */
    int main(){
    scanf("%d%d%d%d%d%d",&n,&a,&b,&f,&fa,&fb);
    S=n*2+1;
    T=S+1;
    for (int i=0;i++<2*n+2;){
    head[i]=NULL;
    }
    for (int i=0;i++<n;){
    int x;
    scanf("%d",&x);
    INSERT(S,i,x,f);
    INSERT(i,S,0,-f);
    (*head[S]).other=head[i];
    (*head[i]).other=head[S];
    INSERT(S,n+i,x,0);
    INSERT(n+i,S,0,0);
    (*head[S]).other=head[n+i];
    (*head[n+i]).other=head[S];
    INSERT(i,T,x,0);
    INSERT(T,i,0,0);
    (*head[i]).other=head[T];
    (*head[T]).other=head[i];
    }
    for (int i=0;i++<n;){
    for (int j=i+a+1;j<=n;j++){
    INSERT(n+i,j,0x7fffffff,fa);
    INSERT(j,n+i,0,-fa);
    (*head[n+i]).other=head[j];
    (*head[j]).other=head[n+i];
    }
    for (int j=i+b+1;j<=n;j++){
    INSERT(n+i,j,0x7fffffff,fb);
    INSERT(j,n+i,0,-fb);
    (*head[n+i]).other=head[j];
    (*head[j]).other=head[n+i];
    }
    }
    // OUT();
    int min_cost=0;
    while (1){
    for (int i=0;i++<T;){
    minc[i]=0x7fffffff;
    }
    minc[S]=su[S]=0;
    minf[S]=0x7fffffff;
    memset(flag,true,sizeof(flag));
    while (!q.empty()){
    q.pop();
    }
    q.push(S);
    while (!q.empty()){
    int v=q.top();
    q.pop();
    if (!flag[v]){
    continue;
    }
    flag[v]=false;
    if (v==T){
    break;
    }
    node *p=head[v];
    while (p!=NULL){
    if ((*p).f&&minc[(*p).t]>(minc[v]+(*p).c)){
    minc[(*p).t]=minc[v]+(*p).c;
    q.push((*p).t);
    flag[(*p).t]=true;
    minf[(*p).t]=min(minf[v],(*p).f);
    su[(*p).t]=v;
    d[(*p).t]=p;
    }
    p=(*p).next;
    }
    }
    if (minc[T]==0x7fffffff){
    break;
    }
    int i=T;
    // printf("!!!%d",T);
    while (su[i]){
    // printf("-%d(%d)",su[i],((*d[i]).c*minf[T]));
    (d[i]).f-=minf[T];
    (
    (*d[i]).other).f+=minf[T];
    min_cost+=((*d[i]).c*minf[T]);
    i=su[i];
    }
    // printf("\n\n");
    // max_flow+=minf[T];
    }
    printf("%d\n",min_cost);
    // OUT();
    return 0;
    }

  • 0
    @ 2010-07-08 20:11:14

    傻傻的问一句:为什么叫“餐巾纸引发的血案”啊…………明明就是餐巾计划问题改版嘛。。。

    是不是起得恐怖一点容易吸引人眼球啊。。。出题人有点不择手段啊……

  • 0
    @ 2010-04-05 22:01:02

    这个...

    我用的拆点,spfa最小费用流,(m:边数(包括反向边),n:点数)

    第一次 40分...n=210,m=300*2;

    最后三个错误号255-RE...

    第二次 40分...n=210,m=500*2;

    第三个TLE 最后两个RE-255...

    第三次 AC...来了个暴力点的:

    n=210,m=200*200*2;

    为啥m=500*2就不行呢...*2是反向边...

    建图:第i天需要a[i]个

    S向点i连flow=a[i],cost=0; 表示第I天结束;

    i+n向T连flow=a[i],cost=0; 表示第i天刚刚开始;

    S向i+n连flow=INF,cost=f;(买的价钱) 表示第i天买花费;

    i向i+n+a连flow=INF,cost=fa; 表示a消毒...

    i向i+n+b连flow=INF,cost=fa; 表示b消毒...

    求最小割最大流...

    这样需要m=500*2为啥不够呢...

  • 0
    @ 2010-03-08 21:26:15

    晕,一开始当成餐巾问题,直接交,40分,后来发现了一个细微的差别:

    餐巾问题第i天用完的餐巾洗了之后,如果洗餐巾花k天,那么第i+k天就可以用

    …………

    但这题,第i天用完之后开始洗,第i+k+1天才可以用,直接导致构图上的差别…………

    之后费用流就行了 o(╯□╰)o

  • 0
    @ 2010-02-28 20:11:15

    此题的fa,fb小心

  • 0
    @ 2009-11-06 21:09:49

    贪心

    编译通过...

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

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

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

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

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

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

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

  • 0
    @ 2009-09-07 14:55:49

    赞cgy4ever。

    其实也可以S向每个i连一条边,容量Inf,费用f。

    当然那个方法更好,只向1连一条边。

  • 0
    @ 2009-08-22 17:18:40

    大家注意了

    本题和原题建图有点不一样!!!

  • 0
    @ 2009-08-20 09:39:49

    标题党...

  • 0
    @ 2009-08-19 19:20:09

    数据弱了,如果上下界的方法不优化在原题是TLE一个点的。

    还是用cgy4ever神牛的方法比较快.

  • 0
    @ 2009-08-02 21:07:19

    听某神牛说过,此题贪心足矣.

    我...

  • 0
    @ 2009-08-02 17:16:21

    cgy4ever建的模型非常经典!

    数据规模小,直接spfa增广就可以解决了。

  • 0
    @ 2009-07-25 15:50:37

    弱弱的问下 我建模的时候采用每一天都可以买毛巾怎么是错的。。。

    即S->i都连一条容量为无穷 费用为f的便。。

    不知道这种和S->1有什么区别。。

  • 0
    @ 2009-07-24 09:29:51

    佩服cgy4ever大牛!!!!

    一般建图是要求上下界的费用流的,一开始多次一举求了最大流

  • 0
    @ 2009-07-17 16:34:45

    典型的最小费用最大流问题 …… 尤其是图是一个二分图 = =||

    建图为 :

    procedure addarc (u , v , c , w : longint) ;

    begin

    // writeln (u,' - > ',v,' : ',c,' : ',w) ;

    inc (tot) ; arc[tot].d := v ; arc[tot].c := c ; arc[tot].w := w ;

    arc[tot].next := vr ; vr := tot ;

    inc (tot) ; arc[tot].d := u ; arc[tot].c := 0 ; arc[tot].w := -w ;

    arc[tot].next := vr[v] ; vr[v] := tot ;

    end ;

    procedure solve ;

    var i , c , n , New_cost , Q_time , Q_cost , S_time , S_cost

    : longint ;

    begin

    fillchar (vr , sizeof (vr) , $ff) ; tot := -1 ;

    // readln (n , New_cost , Q_time , Q_cost , S_time , S_cost) ;

    readln (n , Q_time , S_time , New_cost , Q_cost , S_cost) ;

    s := n + n + 1 ; t := s + 1 ; z := t ;

    for i := 1 to n do begin

    read (c) ;

    addarc (s , i , c , 0) ;

    addarc (n + i , t , c , 0) ;

    addarc (s , n + i , oo , New_cost) ;

    if (i + Q_time

信息

ID
1552
难度
5
分类
图结构 | 网络流 点击显示
标签
(无)
递交数
300
已通过
104
通过率
35%
被复制
1
上传者