哪裡錯了?

#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> u;
vector<int> pre;
vector<int> vis;
vector<vector<int> > c;
vector<vector<int> > p; 
deque<int> q;

int bfs_1(int s,int t,int *flow,int *cost)
{
    f.resize(0);
    f.resize(c.size(),0);
    f[s]=oo_max;
    u.resize(0);
    u.resize(c.size(),oo_max);
    u[s]=0;
    pre.resize(0);
    pre.resize(c.size(),-1);
    pre[s]=0;
    vis.resize(0);
    vis.resize(c.size(),0);
    q.resize(0);
    for (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<c.size();i++)
            if (c[now][i]&&u[now]+p[now][i]<u[i])
            {
                pre[i]=now;
                f[i]=min(c[now][i],f[now]);
                u[i]=u[now]+p[now][i];
                if (vis[i]==0)
                    vis[i]=1,q.push_back(i);
            }
    }
    *flow=f[t];
    *cost=u[t];
    return ((pre[t]!=-1)?1:0);
}

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

int main()
{
    while (~scanf("%d%d%d",&t,&n,&m))
    {
        c.resize(0);
        c.resize(t+2);
        for (int i=0;i<c.size();i++)
            c[i].resize(c.size(),0);
        for (int i=0;i<c.size()-1;i++)
            c[i][i+1]=m;
        p.resize(0);
        p.resize(c.size());
        for (int i=0;i<c.size();i++)
            p[i].resize(c.size(),0);
        for (int i=1;i<=n;i++)
        {
            int x,y,v;
            scanf("%d%d%d",&x,&y,&v);
            c[x][y+1]=1;
            p[x][y+1]=-v;
            p[y+1][x]=v;
        }
        int ans_flow=0,ans_cost=0;
        min_cost_max_flow(0,c.size()-1,&ans_flow,&ans_cost);
        printf("%d\n",-ans_cost);
    }
}

1 条评论

  • @ 2017-07-12 21:40:17
    #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);
        }
    }
    
  • 1

信息

ID
1525
难度
6
分类
图结构 | 网络流 点击显示
标签
(无)
递交数
520
已通过
148
通过率
28%
上传者