[ACM]CCF CSP [201412-5]E题 货物调度

时间：2022-08-20 21:29:58

更新下：换了zkw费用流，过掉了所有数据。代码最下面，代码很丑就是了。

、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、

费用流：把每个城市按7天拆成7个点，边就很好连了。（类似猪圈那题）。

只拿到【90分】，估计是我的费用流模板太差了。

据说有个zkw费用流很快，什么时候换下。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
struct EDGE{
  int from,to,flow,cap,cost;
  EDGE(int u=0,int v=0,int cp=0,int cst=0){from=u;to=v;flow=0;cap=cp;cost=cst;}
};
/*
  用法:(1) clearMap
       (2) addEdge    节点个数由addEdge自动计算
       (3) solve(s,t,&flow,&cost) 计算s->t的最小费用最大流,费用保存在cost中，流保留在flow中
*/
class MCMF{                                  //对费用流进行类似ISAP的优化
  #define MCMFINF 0x7fff0000
  #define MCMFN   1010
private:
  int  s,t;
  int  n;                                    //n在添加边时自动维护，节点下标范围[0..n]
  int  p[MCMFN];
  int  d[MCMFN];
  bool inq[MCMFN];
  vector<EDGE> e;
  vector<int>  g[MCMFN];
  bool spfa(int &flow,int &cost);            //是否能找到一条增广路
  int  augument(int &flow,int& cost);        //对p中的路径进行增广，流量和费用加在flow和cost中
public:
  int  clearMap();
  int  addEdge(int u,int v,int cap,int cost);  //添加一条单向边
  int  solve(int s,int t,int& flow,int&cost);  //求解s->t的费用流
};
int MCMF::clearMap(){
  n=0;
  e.clear();
  for (int i=0;i<MCMFN;i++)g[i].clear();
  return 0;
}
int MCMF::addEdge(int u,int v,int cap,int cost){
  if (cap==0) return 0;
  n=max(n,u);
  n=max(n,v);
  e.push_back(EDGE(u,v,cap,cost));
  e.push_back(EDGE(v,u,0,-cost));
  g[u].push_back(e.size()-2);
  g[v].push_back(e.size()-1);
  //printf("(%d->%d) cap=%d cost=%d\n",u,v,cap,cost);
  return 0;
}
int MCMF::augument(int& flow,int& cost){
  int x=t;
  int mi_flow=MCMFINF;    //增广路可以通过的流量
  int cost2  =0;          //单位流量的cost
  while (x!=s){
    EDGE ed=e[p[x]];
    mi_flow=min(mi_flow,ed.cap-ed.flow);
    cost2 +=ed.cost;
    x=ed.from;
  }
  //边的流量增加
  x=t;
  while(x!=s){
    e[p[x]].flow+=mi_flow;
    e[p[x]^1].flow-=mi_flow;
    x=e[p[x]].from;
  }
  //
  flow+=mi_flow;
  cost+=cost2*mi_flow;
  return 0;
}
bool MCMF::spfa(int& flow,int& cost){
  for (int i=0;i<=n;i++)d[i]=MCMFINF;
  memset(inq,0,sizeof(inq));
  d[s]=0;
  inq[s]=true;
  //spfa
  queue<int> Q;
  Q.push(s);
  while (!Q.empty()){
     int u=Q.front();Q.pop();
     inq[u]=false;
     for (int i=0;i<g[u].size();i++){
       EDGE ed=e[g[u][i]];
       if (ed.cap>ed.flow && d[ed.to]>d[u]+ed.cost){
         d[ed.to]=d[u]+ed.cost;
         p[ed.to]=g[u][i];
         if (!inq[ed.to]){
           inq[ed.to]=true;
           Q.push(ed.to);
         }
       }
     }
  }
  //printf("d[%d]=%d\n",t,d[t]);
  if (d[t]>=MCMFINF) return false;
  augument(flow,cost);
  return true;
}
int MCMF::solve(int s,int t,int &flow,int& cost){
  flow=cost=0;
  this->s=s;
  this->t=t;
  while (spfa(flow,cost));
  return 0;
}
#define N 1010
MCMF mcmf;
int n,m;
int a[N][8];
int b[N][8];
int w[N];
int v[N];
struct ED{
  int u,v,w;
  ED(int u=0,int v=0,int w=0):u(u),v(v),w(w){}
};
vector<ED>g[N];
void read(){
  scanf("%d%d",&n,&m);
  for (int i=1;i<=n;i++){
    for (int j=1;j<=7;j++)scanf("%d",&a[i][j]);
    for (int j=1;j<=7;j++)scanf("%d",&b[i][j]);
    scanf("%d%d",&v[i],&w[i]);
  }
  for (int i=1;i<=m;i++){
    int u,v,w;
    scanf("%d%d%d",&u,&v,&w);
    g[u].push_back(ED(u,v,w));
    g[v].push_back(ED(v,u,w));
  }
}
#define NODE(city,day) ((city-1)*7+((day)==8?1:(day)))
#define FOR(i,s,t) for (int i=s;i<=t;i++)
void solve(){
  //建图
  int s=n*7+1;
  int t=n*7+2;
  mcmf.clearMap();
  FOR(city,1,n){
    FOR (day,1,7){
      //s->city(i,j) a[i][j] cost=0 产生的货物
      mcmf.addEdge(s,NODE(city,day),a[city][day],0);
      //city(i,j)->t b[i][j] cost=0 消耗的货物
      mcmf.addEdge(NODE(city,day),t,b[city][day],0);
    }
    //货物放到下一天
    FOR(day,1,7) mcmf.addEdge(NODE(city,day),NODE(city,day+1),v[city],w[city]);
    //货物运输到其他城市
    FOR(i,0,g[city].size()-1){
      ED e=g[city][i];
      FOR(day,1,7){
        mcmf.addEdge(NODE(city,day),NODE(e.v,day),0x7fff0000,e.w);
      }
    }
  }
  int flow=0,cost=0;
  mcmf.solve(s,t,flow,cost);
  printf("%d\n",cost);
}
int main(){
  read();
  solve();
  return 0;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////

以下是找了个zkw模板带进入，确实快了。~【100分】

#include <cstdio>
#include <cstring>
#include<vector>
#include <iostream>
using namespace std;
const int maxint=~0U>>1;

/*
  用法:n节点个数。求解节点0到节点n的费用流
  (1)设置n
  (2)addEdge
  (3)solve()
*/
#define N 1000
#define M 50000
int n,m,pi1,cost=0;
bool v[N];
struct etype
{
    int t,c,u;
    etype *next,*pair;
    etype(){}
    etype(int t_,int c_,int u_,etype* next_):
        t(t_),c(c_),u(u_),next(next_){}
    //void* operator new(unsigned,void* p){return p;}
} *e[M];

etype *Pe=new etype[M];

int aug(int no,int m)
{
    if(no==n)return cost+=pi1*m,m;
    v[no]=true;
    int l=m;
    for(etype *i=e[no];i;i=i->next)
        if(i->u && !i->c && !v[i->t])
        {
            int d=aug(i->t,l<i->u?l:i->u);
            i->u-=d,i->pair->u+=d,l-=d;
            if(!l)return m;
        }
    return m-l;
}

bool modlabel()
{
    int d=maxint;
    for(int i=1;i<=n;++i)if(v[i])
        for(etype *j=e[i];j;j=j->next)
            if(j->u && !v[j->t] && j->c<d)d=j->c;
    if(d==maxint)return false;
    for(int i=1;i<=n;++i)if(v[i])
        for(etype *j=e[i];j;j=j->next)
            j->c-=d,j->pair->c+=d;
    pi1 += d;
    return true;
}
int solve(){
    cost=0;
    do do memset(v,0,sizeof(v));
    while(aug(1,maxint));
    while(modlabel());
    return cost;
}
void addEdge(int s,int t,int u,int c){
    e[s]=new(Pe++)etype(t, c,u,e[s]);
    e[t]=new(Pe++)etype(s,-c,0,e[t]);
    e[s]->pair=e[t];
    e[t]->pair=e[s];

}
struct ED{
  int u,v,w;
  ED(int u=0,int v=0,int w=0):u(u),v(v),w(w){}
};
struct PROBLEM{
int n,m;
int a[N][8];
int b[N][8];
int w[N];
int v[N];
vector<ED>g[N];
void read(){
  scanf("%d%d",&n,&m);
  for (int i=1;i<=n;i++){
    for (int j=1;j<=7;j++)scanf("%d",&a[i][j]);
    for (int j=1;j<=7;j++)scanf("%d",&b[i][j]);
    scanf("%d%d",&v[i],&w[i]);
  }
  for (int i=1;i<=m;i++){
    int u,v,w;
    scanf("%d%d%d",&u,&v,&w);
    g[u].push_back(ED(u,v,w));
    g[v].push_back(ED(v,u,w));
  }
}

#define NODE(city,day) (((city-1)*7+((day)==8?1:(day)))+1)
#define FOR(i,s,t) for (int i=s;i<=t;i++)
void solve(){
  //建图
  int s=1;
  int t=n*7+2;
  FOR(city,1,n){
    FOR (day,1,7){
      //s->city(i,j) a[i][j] cost=0 产生的货物
      addEdge(s,NODE(city,day),a[city][day],0);
      //city(i,j)->t b[i][j] cost=0 消耗的货物
      addEdge(NODE(city,day),t,b[city][day],0);
    }
    //货物放到下一天
    FOR(day,1,7) addEdge(NODE(city,day),NODE(city,day+1),v[city],w[city]);
    //货物运输到其他城市
    FOR(i,0,g[city].size()-1){
      ED e=g[city][i];
      FOR(day,1,7){
        addEdge(NODE(city,day),NODE(e.v,day),0x7fff0000,e.w);
      }
    }
  }
}
}problem;
int main()
{
    problem.read();
    problem.solve();
    n=problem.n*7+2;
    printf("%d\n",solve());
    return 0;
}


标签：

相关文章