P2050 [NOI2012]美食节

· · 个人记录

P2050 [NOI2012]美食节

这题一看,与另外一道题很像——P2053 [SCOI2007]修车

仔细分析一下,发现两道题建图方式是几乎一样的。

除了一点:本题中每一种“车”有多个需求。

但是这个好办,连边的时候流量变成p[i]就好了

到此,思路正确了。

但是TLE啊,为什么?

再看一下数据范围——两道题根本就不是一个档次!

超过600W条边,Of\;course\;TLE...

怎么办?

这时候,一个很重要的优化诞生——动态加边

因为每次跑出来只能找到一条增广路,所以可以暂时不连不需要的边。

而spfa最多找出\sum_{i=1}^{n}p[i]条增广路,时间为O(p)

总复杂度为O(np^2),再加上spfa的玄学常数,就可以过了。

附代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#define id(i,j) ((i-1)*p+j+n)
#define l(x) ((x-n-1)/p+1)
#define r(x) ((x-n-1)%p+1)
#define MAXN 100010
#define MAXM 110
#define MAX 999999999
using namespace std;
int n,m,s,t,c=2,p=0,maxflow=0,mincost=0;
int head[MAXN],path[MAXN],deep[MAXN],fa[MAXN],flow[MAXN],time[MAXM][MAXM];
bool vis[MAXN];
struct node{
    int next,to,w,cost;
}a[MAXN*100];
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
inline void add(int u,int v,int w,int cost){//加边
    a[c].to=v;a[c].w=w;a[c].cost=cost;a[c].next=head[u];head[u]=c++;
    a[c].to=u;a[c].w=0;a[c].cost=-cost;a[c].next=head[v];head[v]=c++;
}
inline int relax(int u,int v,int i,int w,int cost){
    if(path[v]>path[u]+cost){
        path[v]=path[u]+cost;
        fa[v]=u;
        deep[v]=i;
        flow[v]=min(w,flow[u]);
        return 1;
    }
    return 0;
}
bool spfa(){
    int u,v;
    queue<int> q;
    for(int i=s;i<=t;i++){path[i]=MAX;vis[i]=false;fa[i]=-1;flow[i]=0;}
    path[s]=0;
    vis[s]=true;
    fa[s]=0;
    flow[s]=MAX;
    q.push(s);
    while(!q.empty()){
        u=q.front();
        q.pop();
        vis[u]=false;
        for(int i=head[u];i;i=a[i].next){
            v=a[i].to;
            if(a[i].w&&relax(u,v,i,a[i].w,a[i].cost)&&!vis[v]){
                vis[v]=true;
                q.push(v);
            }
        }
    }
    if(path[t]==MAX)return false;
    return true;
}
void EK(){
    while(spfa()){//动态加边版EK
        for(int i=t;i!=s;i=fa[i]){
            a[deep[i]].w-=flow[t];
            a[deep[i]^1].w+=flow[t];
        }
        maxflow+=flow[t];
        mincost+=flow[t]*path[t];
        int u=a[deep[t]^1].to;
        add(u+1,t,1,0);
        for(int i=1;i<=n;i++)add(i,u+1,1,time[i][l(u+1)]*r(u+1));//加上对应的下一组边
    }
    printf("%d\n",mincost);
}
void init(){//读入+预处理
    n=read();m=read();
    s=0;
    for(int i=1;i<=n;i++){
        int x=read();
        p+=x;
        add(s,i,x,0);
    }
    t=n+p*m+1;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        time[i][j]=read();
        add(i,id(j,1),1,time[i][j]);
    }
    for(int i=1;i<=m;i++)add(id(i,1),t,1,0);
}
int main(){//主函数So easy!
    init();
    EK();
    return 0;
}