题做多的话不难想到可能是以行列作为二分图两个点集,然后网络流相关

具体怎么弄呢

我们可以用求补集的思想,假设有解

我们先把棋盘能放的地方放满士兵,然后我们尽量的把士兵拿走

并且要满足行和列的要求,

说到这方法就很明显了

ans=n*m-障碍数-最大流

我们用x[i]表示棋盘放满后第i行最多能移开的士兵数

y[i]表示棋盘放满后第i列最多能移开的士兵数

然后建图就更明显了,不多说

无解预先判断一下即可

 const inf=;
type node=record
       next,point,flow:longint;
     end; var edge:array[..] of node;
    he,li,cur,p,numh,pre,h,d:array[..] of longint;
    a:array[..,..] of boolean;
    k,i,j,n,m,x,y,len,t:longint; function min(a,b:longint):longint;
  begin
    if a>b then exit(b) else exit(a);
  end; procedure add(x,y,f:longint);
  begin
    inc(len);
    edge[len].point:=y;
    edge[len].flow:=f;
    edge[len].next:=p[x];
    p[x]:=len;
  end; function sap:longint;
  var u,i,j,neck,tmp,q:longint;
  begin
    neck:=inf;
    u:=;
    numh[]:=t+;
    h[]:=;
    sap:=;
    for i:= to t do
      cur[i]:=p[i];
    while h[]<t+ do
    begin
      d[u]:=neck;
      i:=cur[u];
      while i<>- do
      begin
        j:=edge[i].point;
        if (edge[i].flow>) and (h[u]=h[j]+) then
        begin
          neck:=min(neck,edge[i].flow);
          pre[j]:=u;
          cur[u]:=i;
          u:=j;
          if u=t then
          begin
            sap:=sap+neck;
            while u<> do
            begin
              u:=pre[u];
              j:=cur[u];
              dec(edge[j].flow,neck);
              inc(edge[j xor ].flow,neck);
            end;
            neck:=inf;
          end;
          break;
        end;
        i:=edge[i].next;
      end;
      if i=- then
      begin
        dec(numh[h[u]]);
        if numh[h[u]]= then exit;
        tmp:=t;
        i:=p[u];
        q:=-;
        while i<>- do
        begin
          j:=edge[i].point;
          if edge[i].flow> then
            if h[j]<tmp then
            begin
              tmp:=h[j];
              q:=i;
            end;
          i:=edge[i].next;
        end;
        h[u]:=tmp+;
        cur[u]:=q;
        inc(numh[h[u]]);
        if u<> then
        begin
          u:=pre[u];
          neck:=d[u];
        end;
      end;
    end;
  end; begin
  len:=-;
  fillchar(p,sizeof(p),);
  readln(n,m,k);
  t:=n+m+;
  for i:= to n do
    read(he[i]);
  for i:= to m do
    read(li[i]);
  for i:= to k do
  begin
    readln(x,y);
    a[x,y]:=true;
    inc(he[x]);
    inc(li[y]);
  end;
  for i:= to n do
  begin
    if he[i]>m then
    begin
      writeln('JIONG!');
      halt;
    end;
    add(,i,m-he[i]);
    add(i,,);
  end;
  for i:= to m do
  begin
    if li[i]>n then
    begin
      writeln('JIONG!');
      halt;
    end;
    add(i+n,t,n-li[i]);
    add(t,i+n,);
  end;
  for i:= to n do
    for j:= to m do
      if not a[i,j] then
      begin
        add(i,j+n,);
        add(j+n,i,);
      end;
  writeln(n*m-k-sap);
end.

最新文章

  1. 理解浏览器历史记录(2)-hashchange、pushState
  2. Java数据结构和算法之递归
  3. 第四十六课:MVC和MVVM的开发区别
  4. 活动组件(三):Intent
  5. paper 86:行人检测资源(上)综述文献【转载,以后使用】
  6. Java DESede用C++ Openssl实现
  7. flex/bison 计算器
  8. 【转】ubuntu连接android设备(附最简单方法)
  9. DEDE栏目内容调用
  10. [Swust OJ 247]--皇帝的新衣(组合数+Lucas定理)
  11. 使用JDBC进行数据库的事务操作(2)
  12. JS 精度问题处理
  13. NOIP2000提高组复赛C 单词接龙
  14. 删除对象的某个属性 delete
  15. The absolute uri: http://java.sun.com/jsp/jstl/core cannot be resolved in either web.xml or the jar files deployed with this application问题解决方案参考
  16. 让BIND9对任意域名查询都返回固定的IP地址
  17. Markdown页内跳转实现方法
  18. tensorflow(深度学习框架)详细讲解及实战
  19. Atitit 路径规划法attilax总结 扫描线路法
  20. ECharts学习(1)--toolbox(工具栏)

热门文章

  1. js 函数命名
  2. C10K问题和Libevent库介绍
  3. java线程中生产者与消费者的问题
  4. javaIo流实际应用
  5. 初用jquery
  6. 使用JS实现鼠标滚轮事件
  7. vagrant 设置除默认工项目之外的synced_folder一个坑
  8. vs2012生成的项目,如何在只装有VS2010的电脑上打开
  9. Eclipse中的add jars和add external jars有什么区别(转载)
  10. java中关于移位运算符的demo与总结