题解

7 条题解

  • 1
    @ 2017-10-07 10:39:44
    #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;
    vector<int> a;
    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*temp_flow);
        }
    }
    
    int main()
    {
        while (~scanf("%d%d",&n,&m))
        {
            cw.resize(0);
            cw.resize(n+3);
            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);
            }
            a.resize(0);
            a.resize(n+2,0);
            for (int i=1;i<=n;i++)
                scanf("%d",&a[i]);
            for (int i=1;i<=m;i++)
            {
                int a,b,c;
                scanf("%d%d%d",&a,&b,&c);
                add_edge_1(a,b+1,oo_max,c);
            }
            for (int i=1;i<=n+1;i++)
            {
                int flow=a[i]-a[i-1];
                if (flow>0)
                    add_edge_1(0,i,flow,0);
                else if (flow<0)
                    add_edge_1(i,cw.size()-1,-flow,0);
                if (i>1)
                    add_edge_1(i,i-1,oo_max,0);
            }
            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
    @ 2018-06-24 08:41:13

    看成线性规划,对偶之后可以证明得到的矩阵是全幺模的,直接单纯形。

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int MAXSIZE=10000020;
    const ll INF=0x3f3f3f3f3f3f3f3fLL;
    int bufpos;
    char buf[MAXSIZE];
    #define NEG 0
    void init(){
        #ifdef LOCAL
            freopen("1061.txt","r",stdin);
        #endif
        buf[fread(buf,1,MAXSIZE,stdin)]='\0';
        bufpos=0;
    }
    #if NEG
    int readint(){
        bool isneg;
        int val=0;
        for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
        bufpos+=(isneg=buf[bufpos]=='-');
        for(;isdigit(buf[bufpos]);bufpos++)
            val=val*10+buf[bufpos]-'0';
        return isneg?-val:val;
    }
    #else
    int readint(){
        int val=0;
        for(;!isdigit(buf[bufpos]);bufpos++);
        for(;isdigit(buf[bufpos]);bufpos++)
            val=val*10+buf[bufpos]-'0';
        return val;
    }
    #endif
    char readchar(){
        for(;isspace(buf[bufpos]);bufpos++);
        return buf[bufpos++];
    }
    int readstr(char* s){
        int cur=0;
        for(;isspace(buf[bufpos]);bufpos++);
        for(;!isspace(buf[bufpos]);bufpos++)
            s[cur++]=buf[bufpos];
        s[cur]='\0';
        return cur;
    }
    int n,m;
    ll a[10005][1005];
    void pivot(int e,int l){ //e,n+l;
        ll tmp=-a[l][e];
        a[l][e]=-1;
        for(int i=0;i<=n;i++)
            a[l][i]/=tmp;
        for(int i=0;i<=m;i++)
            if (i!=l && a[i][e]){
                ll tmp=a[i][e];
                a[i][e]=0;
                if (tmp==1)
                    for(int j=0;j<=n;j++)
                        a[i][j]+=a[l][j];
                else if (tmp==-1)
                    for(int j=0;j<=n;j++)
                        a[i][j]-=a[l][j];
                else for(int j=0;j<=n;j++)
                    a[i][j]+=tmp*a[l][j];
            }
    }
    ll work(){
        while(1){
            ll mx=0,x=0;
            for(int i=1;i<=n;i++)
                if (a[0][i]>mx)
                    mx=a[0][i],x=i;
            if (!x)
                return a[0][0];
            ll mn=INF,y=0;
            for(int i=1;i<=m;i++){
                if (a[i][x]>=0)
                    continue;
                ll tmp=-a[i][0]/a[i][x];
                if (tmp<mn)
                    mn=tmp,y=i;
            }
            if (!y){
                puts("WTF");
                return INF;
            }
            pivot(x,y);
        }
    }
    int main(){
        init();
        n=readint(),m=readint();
        for(int i=1;i<=n;i++)
            a[0][i]=readint();
        for(int i=1;i<=m;i++){
            int l=readint(),r=readint();
            a[i][0]=readint();
            for(int j=l;j<=r;j++)
                a[i][j]=-1;
        }
        printf("%lld",work());
    }
    
  • 0
    @ 2017-03-02 09:41:26

    神奇的费用流....
    Orz楼下学长QwQ

    #include <bits/stdc++.h>
    using namespace std;
    
    const int MAXN = 1005, MAXM = 200000; 
    struct node {
        int to, next, f, c, neg;
    } edge[MAXM];
    int head[MAXN], top = 0;
    void push(int i, int j, int k, int l)
    {
        //printf("%d--%d,%d-->%d\n", i, k, l, j);
        ++top, edge[top] = (node) {j, head[i], k, l, top+1}, head[i] = top;
        ++top, edge[top] = (node) {i, head[j], 0, -l, top-1}, head[j] = top;
    }
    int n, m;
    int S = 1002, T = 1003;
    const int inf = 23333333;
    
    void push_lim(int i, int j, int low)
    {
        push(S, j, low, 0);
        push(i, T, low, 0);
        push(i, j, inf, 0);
    }
    
    int vis[MAXN], dis[MAXN];
    int pre[MAXN], pre_edge[MAXN];
    queue<int> que;
    
    bool spfa()
    {
        memset(vis, 0, sizeof vis);
        memset(dis, 127/3, sizeof dis);
        memset(pre, 0, sizeof pre);
        vis[S] = 1, dis[S] = 0, que.push(S);
        while (!que.empty()) {
            int tp = que.front(); que.pop(); vis[tp] = 0;
            for (int i = head[tp]; i; i = edge[i].next) {
                if (edge[i].f == 0 || dis[edge[i].to] <= dis[tp] + edge[i].c) continue;
                dis[edge[i].to] = dis[tp] + edge[i].c;
                pre[edge[i].to] = tp;
                pre_edge[edge[i].to] = i;
                if (!vis[edge[i].to])
                    vis[edge[i].to] = 1, que.push(edge[i].to);
            }
        }
        return dis[T] <= inf;
    }
    
    int work(int &cost)
    {
        int ans = inf;
        for (int i = T; i != S; i = pre[i]) ans = min(ans, edge[pre_edge[i]].f);
        for (int i = T; i != S; i = pre[i]) edge[pre_edge[i]].f -= ans, edge[edge[pre_edge[i]].neg].f += ans;
        cost += dis[T]*ans;
        //cout << dis[T] << "--" << endl;
        //cin.get();
        return ans;
    }
    
    int mcf(int &cost)
    {
        int ans = 0;
        while (spfa()) ans += work(cost);
        return ans; 
    }
    
    int main() 
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            int u; scanf("%d", &u);
            push_lim(i, i+1, u);
        }
        for (int i = 1; i <= m; i++) {
            int s, t, c; scanf("%d%d%d", &s, &t, &c);
            push(t+1, s, inf, c);
        }
        int cost = 0;
        mcf(cost);
        cout << cost << endl; 
        return 0;
    }
    
  • 0
    @ 2016-06-13 21:53:22

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>

    const int maxN=1005;
    const int maxM=10005;
    const int inf=0x7f7f7f7f;

    struct Edge
    {
    int to;
    int next;
    int capacity;
    int cost;

    void assign(int t,int n,int cp,int co)
    {
    to=t,next=n,capacity=cp,cost=co;
    }
    };

    Edge elist[maxM*20];
    int head[maxN];
    int ecnt;
    int src,sink;

    void initEdge()
    {
    memset(head,-1,sizeof(head));
    ecnt=0;
    }

    inline void addEdge(int from,int to,int capacity,int cost)
    {
    elist[ecnt].assign(to,head[from],capacity,cost);
    head[from]=ecnt++;
    elist[ecnt].assign(from,head[to],0,-cost);
    head[to]=ecnt++;
    }

    int N,M;
    int A[maxN];
    int S[maxM],T[maxM],C[maxM];

    void input()
    {
    scanf("%d%d",&N,&M);
    A[0]=0; A[N+1]=0;
    for(int i=1;i<=N;i++) scanf("%d",A+i);
    for(int i=1;i<=M;i++)
    scanf("%d%d%d",S+i,T+i,C+i);
    }

    void buildGraph()
    {
    src=0; sink=N+2;
    initEdge();
    for(int i=1;i<=N+1;i++)
    {
    if(A[i]-A[i-1]>0) addEdge(i,sink,A[i]-A[i-1],0);
    else if(A[i]-A[i-1]<0) addEdge(src,i,A[i-1]-A[i],0);
    }
    for(int i=1;i<=N;i++)
    addEdge(i,i+1,inf,0);
    for(int i=1;i<=M;i++)
    addEdge(T[i]+1,S[i],inf,C[i]);
    }

    int dist[maxN];
    int prevV[maxN];
    int prevE[maxN];
    bool inq[maxN];
    std::queue<int> que;

    bool spfa()
    {
    memset(dist,0x7f,sizeof(dist));
    dist[src]=0;
    memset(inq,0,sizeof(inq));
    que.push(src);
    prevV[src]=prevE[src]=-1;
    while(!que.empty())
    {
    int cur=que.front();
    que.pop(); inq[cur]=false;
    for(int e=head[cur];e!=-1;e=elist[e].next)
    if(elist[e].capacity)
    {
    int& to=elist[e].to;
    int& co=elist[e].cost;
    if(dist[to]>dist[cur]+co)
    {
    dist[to]=dist[cur]+co;
    prevV[to]=cur;
    prevE[to]=e;
    if(!inq[to])
    {
    que.push(to);
    inq[to]=true;
    }
    }
    }
    }
    return dist[sink]<inf;
    }

    int minCostFlow()
    {
    int res(0);
    while(spfa())
    {
    int maxf=inf;
    for(int e=prevE[sink],v=sink;e!=-1;v=prevV[v],e=prevE[v])
    maxf=std::min(maxf,elist[e].capacity);
    for(int e=prevE[sink],v=sink;e!=-1;v=prevV[v],e=prevE[v])
    {
    res+=maxf*elist[e].cost;
    elist[e].capacity-=maxf;
    elist[e^1].capacity+=maxf;
    }
    }
    return res;
    }

    int main()
    {
    input();
    buildGraph();
    printf("%d\n",minCostFlow());
    return 0;
    }

    Orz ByVoid大神

  • 0
    @ 2016-05-18 14:51:20

    建模好难想得到,费用流……
    ```c++
    #include<cstdio>
    #include<vector>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    using namespace std;

    const int INF=2147483647;

    struct Ed
    {
    int from,to,cap,cost,flow;
    Ed(int a,int b,int c=INF,int e=0,int d=0) : from(a),to(b),cap(c),cost(e),flow(d) {};
    };

    struct Po
    {
    int th;
    vector<int > id_edges;
    Po(int a) : th(a) {};
    };

    int n,m;
    long long int all_cost=0;
    int a[1100],c[1100],p[1100],leastpe[1100];
    vector<Ed> edges;
    vector<Po> points;
    bool inqu[1100];

    void add_edges(int from,int to,int cap,int cost)
    {
    edges.push_back(Ed(from,to,cap,cost));
    points[from].id_edges.push_back(edges.size()-1);
    edges.push_back(Ed(to,from,0,-1*cost));
    points[to].id_edges.push_back(edges.size()-1);
    /*return points[from].id_edges[points[from].id_edges.size()-1];*/
    }

    bool SPFA()
    {
    memset(a,0,sizeof(a));
    memset(c,-1,sizeof(c));
    memset(p,0,sizeof(p));
    memset(inqu,0,sizeof(inqu));
    queue<int> Q;
    a[0]=INF; c[0]=0;
    Q.push(0); inqu[0]=true;
    while(!Q.empty())
    {
    int k=Q.front();Q.pop(); inqu[k]=false;
    Po &now=points[k];

    for(int i=0;i<(int)now.id_edges.size();i++)
    {
    Ed &now_ed=edges[now.id_edges[i]];
    if(now_ed.flow<now_ed.cap&&(c[now_ed.to]==-1||c[now_ed.to]>c[now.th]+now_ed.cost))
    {
    a[now_ed.to]=min(a[now.th],now_ed.cap-now_ed.flow);
    p[now_ed.to]=now.id_edges[i];
    c[now_ed.to]=c[now.th]+now_ed.cost;
    if(!inqu[now_ed.to]) { Q.push(now_ed.to); inqu[now_ed.to] =true; }
    }
    }
    }
    if(a[n+2]==0) return false;
    all_cost+=(long long int)a[n+2]*(long long int)c[n+2];
    for(int i=n+2;i!=0;i=edges[p[i]].from)
    {
    edges[p[i]].flow+=a[n+2];
    edges[p[i]^1].flow-=a[n+2];
    }
    return true;
    }

    int main()
    {
    /*freopen("employee.in","r",stdin);*/
    memset(leastpe,0,sizeof(leastpe));
    scanf("%d%d",&n,&m);
    points.push_back(Po(0));
    for(int i=1;i<=n;i++)
    {
    scanf("%d",&leastpe[i]);
    points.push_back(Po(i));
    }
    points.push_back(Po(n+1));points.push_back(Po(n+2));
    for(int i=1;i<=n+1;i++)
    if(leastpe[i]-leastpe[i-1]>0) add_edges(i,n+2,(leastpe[i]-leastpe[i-1]),0);
    else if(leastpe[i]-leastpe[i-1]<0) add_edges(0,i,(leastpe[i]-leastpe[i-1])*(-1),0);
    for(int i=1;i<=m;i++)
    {
    int b,e,c;
    scanf("%d%d%d",&b,&e,&c);
    add_edges(e+1,b,INF,c);
    /*workgroup_id[i]=add_edges(e+1,b,INF,c);*/
    }
    for(int i=2;i<=n+1;i++) add_edges(i-1,i,INF,0);

    while(SPFA()) {}

    printf("%lld\n",all_cost);
    return 0;
    }
    ```

  • 0
    @ 2016-05-18 14:50:09
    
    
  • 0
    @ 2013-11-03 12:44:08

    这题的难度是10?第一次见到,一直以为4就是最高了。。。 ZKW费用流。。。
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 564 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 564 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 560 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 576 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 608 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 648 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 860 KiB, score = 10
    测试数据 #7: Accepted, time = 31 ms, mem = 1020 KiB, score = 10
    测试数据 #8: Accepted, time = 46 ms, mem = 1236 KiB, score = 10
    测试数据 #9: Accepted, time = 93 ms, mem = 1728 KiB, score = 10
    Accepted, time = 185 ms, mem = 1728 KiB, score = 100
    #include <cstdio>
    #include <algorithm>
    #include <cstring>

    using namespace std;

    #define MAXN 1010

    struct node {
    int t,f,c;
    node *next,*pair;
    node (){
    next=pair=NULL;
    }
    };

    node *head[MAXN];

    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;
    p=new(node);
    p->t=s;
    p->f=0;
    p->c=-c;
    p->next=head[t];
    head[t]=p;
    head[s]->pair=head[t];
    head[t]->pair=head[s];
    }

    int n,m;
    int S,T;
    int a[MAXN];

    int dist[MAXN];
    bool f[MAXN];
    int cost=0;

    int aug(int v,int flow){
    if (v==T){
    cost+=flow*dist[S];
    return flow;
    }
    f[v]=false;
    int rec=0;
    for (node *p=head[v];p;p=p->next){
    if (p->f&&f[p->t]&&dist[v]==dist[p->t]+p->c){
    int ret=aug(p->t,min(flow-rec,p->f));
    p->f-=ret;
    p->pair->f+=ret;
    if ((rec+=ret)==flow){
    return flow;
    }
    }
    }
    return rec;
    }

    bool relabel(){
    int delta=0x7fffffff;
    for (int i=0;i++<T;){
    if (!f[i]){
    for (node *p=head[i];p;p=p->next){
    if (p->f&&f[p->t]){
    delta=min(delta,dist[p->t]+p->c-dist[i]);
    }
    }
    }
    }
    if (delta==0x7fffffff){
    return false;
    }
    for (int i=0;i++<T;){
    if (!f[i]){
    dist[i]+=delta;
    }
    }
    return true;
    }

    int main(){
    memset(head,0,sizeof(head));
    scanf("%d%d",&n,&m);
    S=n+2;
    T=S+1;
    int x=0;
    for (int i=0;i++<n;){
    scanf("%d",&a[i]);
    if (a[i]-x>=0){
    INSERT(S,i,a[i]-x,0);
    } else INSERT(i,T,x-a[i],0);
    x=a[i];
    }
    INSERT(n+1,T,a[n],0);
    for (int i=0;i++<m;){
    int s,t,c;
    scanf("%d%d%d",&s,&t,&c);
    INSERT(s,t+1,0x7fffffff,c);
    }
    for (int i=1;i++<n+1;){
    INSERT(i,i-1,0x7fffffff,0);
    }
    memset(dist,0,sizeof(dist));
    do {
    do {
    memset(f,true,sizeof(f));
    } while (aug(S,0x7fffffff));
    } while (relabel());
    printf("%d\n",cost);
    return 0;
    }

    • @ 2013-11-03 12:45:34

      哦。看走眼了。。。这题是没有难度。。。提交10....

  • 1

信息

ID
1825
难度
4
分类
(无)
标签
递交数
206
已通过
88
通过率
43%
被复制
2
上传者