第i头牛，可以使用第j个防晒霜的，从j到i连一条容量1的边。

每个防晒霜从S给它连容量为cover[i]的边。

求一遍最大流就好了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10000,maxm=5000000,inf=1000000009;
int p[maxm],c[maxm],n1[maxm],q[maxn],h1[maxn],d[maxn],h[maxn],g[maxn];
int l[3000],r[3000],S,T,n,m,k,tot=0,cnt=0,N=0;  char buf[2000000],*pt=buf;
inline int getint(){    int r=0; while(*pt<48||*pt>57)pt++; 
    while(*pt>47&&*pt<58)r=r*10+*pt++-48; return r;
}inline void ae(int x,int y,int z){
    p[tot]=y;   c[tot]=z;   n1[tot]=h[x];   h[x]=tot++;
    p[tot]=x;   c[tot]=0;   n1[tot]=h[y];   h[y]=tot++;
}inline int bfs(){
    memset(d,0xff,sizeof(d));   int r=d[q[0]=S]=0;
    for(int l=0;l<=r;l++)
        for(int k=h[q[l]];~k;k=n1[k])
            if(c[k] && !~d[p[k]])   d[q[++r]=p[k]]=d[q[l]]+1;
    return ~d[T];
}int dfs(int x=S,int lmt=inf){
    if(x==T)    return lmt; int flow;
    for(int &k=g[x];~k;k=n1[k]){
        if(c[k] && d[p[k]]==d[x]+1 && (flow=dfs(p[k],min(lmt,c[k])))){
            c[k]-=flow; c[k^1]+=flow;   return flow;
        }
    }return 0;
}int main(){
    memset(h,-1,sizeof(h));
    fread(pt,1,2000000,stdin);  n=getint(); m=getint(); S=0; T=n+m+1;
    for(int i=1;i<=n;i++)   l[i]=getint(),r[i]=getint(),ae(m+i,T,1);
    for(int i=1;i<=m;i++){
        int u,v; u=getint(),v=getint();  ae(S,i,v);
        for(int j=1;j<=n;j++) if(l[j]<=u&&u<=r[j]) ae(i,m+j,1);
    }int An=0,f=0;   while(bfs()){   memcpy(g,h,sizeof(h));  while(f=dfs())  An+=f;}
    printf("%d\n",An);    return 0;
} 

• 相关文章