题解 P2887 【[USACO07NOV]防晒霜Sunscreen】

大菜鸡fks · 2018-02-08 13:53:10 · 题解

这题我选择使用网络流。做题之前没看题解感觉很像网络流，就试着做了一下，主要是内存原因限制了这题的解法。 1.通过原点向防晒霜建边，边权为cover 2.防晒霜向适合的奶牛建边，复杂度为n²，边权为1 3.奶牛向汇点建边，边权为1, 跑一遍dinic就可以了，实现的时候可以通过开小数组来ac（128mb作者按照建边的规模开貌似会mle）

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=5005;
int spf[maxn],cover[maxn],C,L,c[maxn],l[maxn],r[maxn];
inline void init(){
    scanf("%d%d",&C,&L);
    for (int i=1;i<=C;i++){
        scanf("%d%d",&l[i],&r[i]);
    }
    for (int i=1;i<=L;i++){
        scanf("%d%d",&spf[i],&cover[i]);
    }
}
const int maxm=2000000;
struct edge{
    int link,next,val,opp;
}e[maxm];
int tot,S,T,head[maxn];
inline int get(int x){
    return x+L;
}
inline void add(int u,int v,int w){
    e[++tot]=(edge){v,head[u],w,0}; head[u]=tot;
}
inline void insert(int u,int v,int w){
    add(u,v,w); e[tot].opp=tot+1; add(v,u,0); e[tot].opp=tot-1;
}
inline void build(){
    S=0;
    for (int i=1;i<=L;i++){
        for (int j=1;j<=C;j++){
            if (spf[i]>=l[j]&&spf[i]<=r[j]){
                insert(i,get(j),1);
            }
        }
        insert(S,i,cover[i]);
    }
    T=C+L+1;
    for (int i=1;i<=C;i++){
        insert(get(i),T,1);
    }
}
int h,t,q[maxn],dis[maxn];
inline bool bfs(){
    memset(dis,-1,sizeof(dis));
    h=0; t=1; dis[S]=0; q[1]=S;
    while (h<t){
        int u=q[++h];
        for (int i=head[u];i;i=e[i].next){
            int v=e[i].link;
            if (dis[v]==-1&&e[i].val){
                dis[v]=dis[u]+1;
                q[++t]=v;
                if (v==T) return 1;
            }
        }
    }
    return 0;
}
const int inf=1e9;
int cur[maxn],ans;
inline void clean(){
    memcpy(cur,head,sizeof(cur));
}
inline void backflow(int i,int w){
    e[i].val-=w; 
    e[e[i].opp].val+=w;
}
int dinic(int u,int flow){
    if (!flow||u==T) return flow;
    int used=0;
    for (int i=cur[u];i;i=e[i].next){
        int w,v=e[i].link;
        if (dis[u]+1==dis[v]&&e[i].val){
            w=dinic(v,min(flow-used,e[i].val));
            used+=w;
            backflow(i,w);
            if (w) cur[u]=i;
            if (used==flow) return flow;
        }
    }
    if (!used) dis[u]=-1;
    return used;
}
inline void solve(){
    build();
    while (bfs()){
        clean();
        ans+=dinic(S,inf);
    }
    printf("%d\n",ans);
}
int main(){
    init();
    solve();
    return 0;
}