题解 P4311 【士兵占领】

· · 题解

有上下界最小费用流。

几乎就是模板了。

用(u,v,b,c,w)表示一条从u连向v，下界为b，上界为c，费用为w的边，则

对于每一行，连边(s,i,l[i],m,0)

对于每一列，连边(i,t,c[i],n,0)

对于每个点，连边(i,j,0,1,1)

然后改成无源汇网络流，跑一遍费用流即可。

代码(Dinic)：

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i)
#define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i)
#define For(i,a,b) for(i=(a),i<=(b);++i)
#define Forward(i,a,b) for(i=(a),i>=(b);--i)
template<typename T>inline void read(T &x)
{
    T f=1;x=0;char c;
    for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=x*10+(c^48);
    x*=f;
}
using namespace std;
void file()
{
#ifndef ONLINE_JUDGE
    freopen("water.in","r",stdin);
    freopen("water.out","w",stdout);
#endif
}
const int MAXN=811;
static int n,m,k;
static int l[MAXN],c[MAXN];
static int ans;
static struct edge
{
    int v,w,f,nxt;
}p[MAXN*MAXN<<2];
static int head[MAXN],e=1,s,t,ss,tt;
static bool a[MAXN][MAXN];
inline void add(int u,int v,int f,int w,bool laz=1)
{
    p[++e]=(edge){v,w,f,head[u]};head[u]=e;
    if(laz)add(v,u,0,-w,0);
}
inline void init()
{
    read(n);read(m);read(k);
    Rep(i,1,n)read(l[i]);
    Rep(i,1,m)read(c[i]);
    s=n+m+1;t=s+1;ss=t+1;tt=ss+1;
    static int x,y,cnt,cnss=0,cntt=0;
    Rep(i,1,k)read(x),read(y),a[x][y]=true;
    Rep(i,1,n)
    {
        cnt=0;
        Rep(j,1,m)if(!a[i][j])
        {
            ++cnt;
            add(i,n+j,1,1);
        }
        if(cnt<l[i]){cout<<"JIONG!"<<endl;exit(0);}
        add(s,i,cnt-l[i],0);if(l[i])add(ss,i,l[i],0);
        cnss+=l[i];
    }
    Rep(i,1,m)
    {
        cnt=0;
        Rep(j,1,n)if(!a[j][i])++cnt;
        if(cnt<c[i]){cout<<"JIONG!"<<endl;exit(0);}
        add(n+i,t,cnt-c[i],0);if(c[i])add(n+i,tt,c[i],0);
        cntt+=c[i];
    }
    add(ss,t,cntt,0);add(s,tt,cnss,0);
    add(t,s,0xFFFFFFF,0);
}
static int cur[MAXN],fee;
static int vis[MAXN],dis[MAXN];
static deque<int>G;
inline bool spfa(int s,int t)
{
    memset(dis,0x3f,sizeof dis);
    dis[s]=0;G.push_back(s);
    static int u;vis[s]=true;
    while(!G.empty())
    {
        u=G.front();G.pop_front();
        for(register int v=head[u];v;v=p[v].nxt)
            if(p[v].f&&dis[p[v].v]>dis[u]+p[v].w)
            {
                dis[p[v].v]=dis[u]+p[v].w;
                if(!vis[p[v].v])
                {
                    vis[p[v].v]=true;
                    if(G.empty()||dis[p[v].v]<dis[G.front()])
                        G.push_front(p[v].v);
                    else G.push_back(p[v].v);
                }
            }
        vis[u]=false;
    }
    return dis[t]^dis[0];
}
int dfs(int u,int t,int flow=0xFFFFFFF)
{
    if(!flow||u==t)return flow;
    vis[u]=true;int sum=0;
    for(register int &v=cur[u];v;v=p[v].nxt)
        if(!vis[p[v].v]&&p[v].f&&dis[p[v].v]==dis[u]+p[v].w)
        {
            int f=dfs(p[v].v,t,min(flow,p[v].f));
            p[v].f-=f;p[v^1].f+=f;
            fee+=p[v].w*f;sum+=f;flow-=f;
        }
    vis[u]=false;
    return sum;
}
inline void Dinic(int s,int t)
{while(spfa(s,t))memcpy(cur,head,sizeof head),dfs(s,t);}
inline void solve()
{
    Dinic(ss,tt);
    cout<<fee<<endl;
}
int main()
{
    file();
    init();
    solve();
    return 0;
}

Upt:

啊呀被叉了。。。

其实推导没有写错，只是有几条边忘记建了。。。