BZOJ1458:士兵占领(有上下界最小流)

Description

有一个M * N的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了Li个士兵, 第j列至少放置了Cj个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。

Input

第一行两个数M, N, K分别表示棋盘的行数，列数以及障碍的个数。第二行有M个数表示Li。第三行有N个数表示Ci。接下来有K行，每行两个数X, Y表示(X, Y)这个格子是障碍。

Output

输出一个数表示最少需要使用的士兵个数。如果无论放置多少个士兵都没有办法占领整个棋盘，输出”JIONG!” (不含引号)

Sample Input

4 4 4
1 1 1 1
0 1 0 3
1 4
2 2
3 3
4 3

Sample Output

4
数据范围
M, N <= 100, 0 <= K <= M * N

Solution

有源汇上下界最小流……按行和列建二分图，分别向源汇点建立上下界为$[L_i,INF]$和$[C_i,INF]$的边，然后没有障碍点的两两连$[0,1]$的边，跑一遍就完了。

一个上下界网络流讲的很好的博客。注意别忘了$s$和$t$也要与$ss$和$tt$连边！

Code

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<queue>

 #define N (20009)

 #define INF (0x7f7f7f7f)

 using namespace std;

 struct Edge{int to,next,flow;}edge[N*];

 int n,m,k,vis[][];

 int s=,t=,ss=,tt=;

 int Depth[N],A[N];

 int head[N],num_edge;

 queue<int>q;

 inline int read()

 {

     int x=,w=; char c=getchar();

     while (!isdigit(c)) {if (c=='-') w=-; c=getchar();}

     while (isdigit(c)) x=x*+c-'', c=getchar();

     return x*w;

 }

 void add(int u,int v,int l)

 {

     edge[++num_edge].to=v;

     edge[num_edge].next=head[u];

     edge[num_edge].flow=l;

     head[u]=num_edge;

 }

 void Add(int u,int v,int l,int r)

 {

     add(u,v,r-l); add(v,u,);

     A[u]-=l; A[v]+=l;

 }

 int DFS(int x,int low,int t)

 {

     if (x==t || !low) return low;

     int f=;

     for (int i=head[x]; i; i=edge[i].next)

         if (Depth[edge[i].to]==Depth[x]+)

         {

             int Min=DFS(edge[i].to,min(low,edge[i].flow),t);

             edge[i].flow-=Min;

             edge[((i-)^)+].flow+=Min;

             f+=Min; low-=Min;

             if (!low) break;

         }

     if (!f) Depth[x]=-;

     return f;

 }

 bool BFS(int s,int t)

 {

     memset(Depth,,sizeof(Depth));

     Depth[s]=; q.push(s);

     while (!q.empty())

     {

         int x=q.front(); q.pop();

         for (int i=head[x]; i; i=edge[i].next)

             if (!Depth[edge[i].to] && edge[i].flow)

             {

                 Depth[edge[i].to]=Depth[x]+;

                 q.push(edge[i].to);

             }

     }

     return Depth[t];

 }

 int Dinic(int s,int t)

 {

     int ans=;

     while (BFS(s,t)) ans+=DFS(s,INF,t);

     return ans;

 }

 int main()

 {

     n=read(); m=read(); k=read(); s=n+m+; t=s+;

     for (int i=; i<=n; ++i) Add(s,i,read(),INF);

     for (int i=; i<=m; ++i) Add(i+n,t,read(),INF);

     for (int i=; i<=k; ++i) vis[read()][read()]=;

     for (int i=; i<=n; ++i)

         for (int j=; j<=m; ++j)

             if (!vis[i][j]) Add(i,j+n,,);

     int sum=;

     for (int i=; i<=n+m+; ++i)

         if (A[i]>) sum+=A[i], add(ss,i,A[i]), add(i,ss,);

         else add(i,tt,-A[i]), add(tt,i,);

     add(t,s,INF); add(s,t,);

     if (Dinic(ss,tt)!=sum) {puts("JIONG!"); return ;}

     for (int i=head[ss]; i; i=edge[i].next) edge[i].flow=edge[((i-)^)+].flow=;

     for (int i=head[tt]; i; i=edge[i].next) edge[i].flow=edge[((i-)^)+].flow=;

     int flow0=edge[num_edge].flow;

     edge[num_edge].flow=edge[num_edge-].flow=;

     printf("%d\n",flow0-Dinic(t,s));

 }

秒客网