51nod 4547 开垦土地

Question

政府计划在一块n*m的森林里（可以看做一个n行m列的网格），开垦一块长方形土地，用于种植经济作物。但是，在森林的p个位置，存在国家级珍贵植物，因此，开垦的土地因避开这些位置。
政府部门一共提出了Q个开垦计划，计划开垦一个长度为R宽度为C的土地（不可以旋转）。现在需要你帮忙计算，每个开垦计划可以选择的不同位置有多少个。

输入
第一行包含四个整数n,m,p,q。

接下来p行每行包含两个整数x,y，表示第x行第y列存在珍贵植物。

接下来Q行每行包含两个整数r,c。

输出
输出Q行，每行包含一个整数，表示每个开垦计划可以选择的不同位置个数。

输入样例1
2 4 2 2
1 4
2 1
1 3
2 2
输出样例1
2
1

输入样例2
2 3 3 2
1 2
2 3
2 1
1 1
1 2

输出样例2
3
0

Answer 1

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue> 
using namespace std;

int n,m,s,t;
int va[10100],vb[10100],ea[40100],eb[40100],ec[40100];
int vis[401000],d[401000],cur[401000];
long long ans;
struct Edge
{
    int from,to,cap,flow;
    Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f) {};
};
vector<Edge> edges;
vector<int> G[400100];

void add(int x,int y,int z)//单向边
{
    edges.push_back(Edge(x,y,z,0));
    edges.push_back(Edge(y,x,0,0));
    int oo=edges.size();
    G[x].push_back(oo-2);
    G[y].push_back(oo-1);
}
void ad(int x,int y,int z)//双向边
{
    edges.push_back(Edge(x,y,z,0));
    edges.push_back(Edge(y,x,z,0));
    int oo=edges.size();
    G[x].push_back(oo-2);
    G[y].push_back(oo-1);
}

bool BFS()//最小割模板
{
    memset(vis,0,sizeof(vis));
    queue<int> Q;
    Q.push(s);
    d[s]=0;
    vis[s]=1;
    while(!Q.empty())
    {
        int x=Q.front();
        Q.pop();
        for(int i=0;i<(int)(G[x].size());i++) 
        {
            Edge& e=edges[G[x][i]];
            if(!vis[e.to]&&e.cap>e.flow)
            {
                vis[e.to]=1;
                d[e.to]=d[x]+1;
                Q.push(e.to);
            }
        }
    }
    return vis[t];
}

int DFS(int x,int a) //最小割模板
{
    if(x==t||a==0) return a;
    int flow=0,f;
    for(int& i=cur[x];i<(int)(G[x].size());i++) 
    {
        Edge& e=edges[G[x][i]];
        if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0)
        {
            e.flow+=f;
            edges[G[x][i]^1].flow-=f;
            flow+=f;
            a-=f;
            if(a==0) break;
        }
    }
    return flow;
}

int tdhf() //最小割模板
{
    int flow=0,dx;
    while(BFS())
    {
        memset(cur,0,sizeof(cur));
        dx=DFS(s,1e9);
        while(dx) flow+=dx,dx=DFS(s,1e9);
    }
    return flow;
}


void read(int& x) //快读
{
    int f=1;
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    x*=f;
}


int main()
{
    scanf("%d%d",&n,&m);
    int x[40100],y[40100];
    for(int i=2;i<n;i++) read(va[i]),va[i]*=2;//乘2处理
    for(int i=2;i<n;i++) read(vb[i]),vb[i]*=2;
    for(int i=1;i<=m;i++) 
    {
        read(x[i]),read(y[i]),read(ea[i]),read(eb[i]),read(ec[i]);
        ea[i]*=2,eb[i]*=2,ec[i]*=2;
    }
    s=3*n+1;t=s+1;//s和t
    for(int i=1;i<=n;i++)     //①
    {
        ans=ans+va[i]+vb[i];
        add(s,i,va[i]);
        add(i,t,vb[i]);
    }
    add(s,1,2e9);          //②
    add(n,t,2e9);
    for(int i=1;i<=m;i++)
    {
        ans=ans+ea[i]+eb[i];      //累计
        ad(x[i],y[i],ea[i]/2+eb[i]/2+ec[i]);      //④
        add(s,x[i],ea[i]/2);   //③
        add(s,y[i],ea[i]/2);
        add(x[i],t,eb[i]/2);
        add(y[i],t,eb[i]/2);
    }
    printf("%lld",(ans-tdhf())/2);    //减去损失(最小割)
    return 0;
}