DZY 's BLOG

第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;
} 

自己YY出来了？估计应该是比较简单的网络流入门题吧。。

既然每个点(i,j)最多只能通过c[i][j]个蜥蜴。那么很自然地想到拆点。(i,j)→(i,j)'连上容量为c[i][j]的边。(i,j)为入点。(i,j)'为出点。

对于所有有蜥蜴的点，从S给它连一条容量为1的边。对于所有可以跳到外面的点，连到T，容量是c[i][j]。

然后n^4枚举在内部跳来跳去的情况。最后跑网络流就好了。

连T的边的时候我一直在傻×、、一开始算的是到(0,0)的距离≤d、、果然还是太弱了哎、、

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000,maxm=500000,inf=1000000009;
int p[maxm],c[maxm],n1[maxm],q[maxn],h1[maxn],d[maxn],h[maxn],g[maxn],id[25][25];
int S,T,n,m,k,tot=0,cnt=0,N=0;    char s[25];
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(){
    scanf("%d%d%d",&n,&m,&k);   k;   S=0;    T=801;  memset(h,0xff,sizeof(h));
    for(int i=1,j;i<=n;i++) for(scanf("%s",s+1),j=1;j<=m;j++)   if(s[j]-'0'){
        id[i][j]=++cnt;
        ae((id[i][j]<<1)-1,id[i][j]<<1,s[j]-'0');
        if(min(min(i,n-i+1),min(j,m-j+1))<=k)ae(id[i][j]<<1,T,s[j]-'0');
    }for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int ii=1;ii<=n;ii++) for(int jj=1;jj<=m;jj++){
        if(!id[i][j]||!id[ii][jj])  continue;
        if((ii-i)*(ii-i)+(jj-j)*(jj-j)<=k*k)  ae(id[i][j]<<1,(id[ii][jj]<<1)-1,inf);
    }for(int i=1,j;i<=n;i++) for(scanf("%s",s+1),j=1;j<=m;j++) if(s[j]=='L'){
        N++; if(id[i][j])   ae(S,(id[i][j]<<1)-1,1);
    }int An=0,f=0;   while(bfs()){   memcpy(g,h,sizeof(h));  while(f=dfs())  An+=f;}
    printf("%d\n",N-An);    return 0;
}