BZOJ1707: [Usaco2007 Nov]tanning分配防晒霜【最大流】

dzy posted @ 2013年6月11日 18:13 in BZOJ with tags 最大流 bzoj 网络流 , 1895 阅读

第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;
} 
Avatar_small
Digital Ali 说:
2021年9月06日 21:15

A very excellent blog post. I am thankful for your blog post. I have found a lot of approaches after visiting your post. 123movie

Avatar_small
99employee.com 说:
2023年6月09日 13:56

On our website we collect information of any individual only when they post a comment or reply to any of the commence on our posts. And the only information stored will be the details provided by you along with 99employee.com the posting IP address for security and analysis purposes. On our website we collect information of any individual only when they post a comment or reply to any of the commence on our posts. And the only information stored will be the details provided by you along with the posting IP address for security and analysis purposes.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter