HUST 1027 Enemy Target!

Description

In the Game Red Alert, a group of soviet infantry marches towards our base. And we have N Prism Tanks to defend our base. Suppose the coming infantry marches in a ROW*COLUMN rectangle grid, and keeps the shape unchanged. A Prism Tank can eliminate infantry in any row or column at a shot. Prism Tank is weak in self-defense, so your task is to assign the least Prism Tanks, fire simultaneously to eliminate all the invading enemies. If our Prism Tank is enough, submit any assignment using the least Prism Tanks. Otherwise, report it.

Input

First line: 3 integers ROW,COLUMN,N--number of Prism Tanks we have now(ROW<=1000, COLUMN<=1000,N<=1000). Line 2 to ROW+1: Each line is a binary 01 string with length COLUMN, represent the shape of infantry. Set 1 if a position have a soldier, otherwise 0.

Output

If there exist an assignment, output it in the format: k1+k2 ROW: R1 R2...Rk1 COLUMN: C1 C2...Ck2 k1+k2 is the totoal number of Prism Tanks. Otherwise print one line "NOT ENOUGH TANK".

Sample Input

4 4 4

0101

1010

1010

0010

Sample Output

3

ROW: 1

COLUMN: 1 3

二分圖的最小點集覆寫，這題還需要求出是那些點，直接貪心的方案是錯的

具體的辦法詳見​​正解​​，順便附上本人代碼。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<iostream>
#include<stack>
#include<algorithm>
#include<bitset>
#include<functional>
#include<ctime>
using namespace std;
typedef unsigned long long ull;
typedef long long LL;
const int maxn = 1e3 + 10;
const int INF = 0x7FFFFFFF;
int n, m, k, flag[maxn * 2], ans;
char s[maxn];

struct MaxFlow
{
  const static int maxe = 2e6 + 10;    //邊數
  const static int maxp = 1e5 + 10;   //點數
  const static int INF = 0x7FFFFFFF;
  struct Edges
  {
    int x, f;
    Edges(){}
    Edges(int x, int f) :x(x), f(f){}
  }edge[maxe];
  int first[maxp], next[maxe], dis[maxp], tot, work[maxp], n;

  void clear(int x){ n = x; tot = 0; for (int i = 0; i <= n; i++) first[i] = -1; }

  void AddEdge(int s, int t, int f)
  {
    edge[tot] = Edges(t, 0); next[tot] = first[s]; first[s] = tot++;
    edge[tot] = Edges(s, f); next[tot] = first[t]; first[t] = tot++;
  }

  bool bfs(int s, int t)
  {
    for (int i = 0; i <= n; i++) dis[i] = -1;
    queue<int> p;    p.push(s);    dis[s] = 0;
    while (!p.empty())
    {
      int q = p.front();    p.pop();
      for (int i = first[q]; i != -1; i = next[i])
      {
        if (edge[i ^ 1].f&&dis[edge[i].x] == -1)
        {
          p.push(edge[i].x);
          dis[edge[i].x] = dis[q] + 1;
          if (dis[t] != -1) return true;
        }
      }
    }
    return false;
  }

  int dfs(int s, int t, int low)
  {
    if (s == t) return low;
    for (int &i = work[s], x; i >= 0; i = next[i])
    {
      if (dis[s] + 1 == dis[edge[i].x] && edge[i ^ 1].f && (x = dfs(edge[i].x, t, min(low, edge[i ^ 1].f))))
      {
        edge[i].f += x;    edge[i ^ 1].f -= x;  return x;
      }
    }
    return 0;
  }

  int dinic(int s, int t)
  {
    int maxflow = 0, inc = 0;
    while (bfs(s, t))
    {
      for (int i = 0; i <= n; i++) work[i] = first[i];
      while (inc = dfs(s, t, INF)) maxflow += inc;
    }
    return maxflow;
  }
  void dfs(int x, int y)
  {
    if (flag[x] >= 0 || !x || x == n) return;
    flag[x] = y;
    for (int i = first[x]; i != -1; i = next[i]) dfs(edge[i].x, y ^ 1);
  }
  void find(int a, int b)
  {
    memset(flag, -1, sizeof(flag));
    for (int i = first[0]; i != -1; i = next[i])
    {
      if (!edge[i].f) dfs(edge[i].x, 0);
    }
    for (int i = 1; i <= a; i++) if (flag[i] == -1) flag[i] = 1;
    for (int i = a + 1; i <= a + b; i++) if (flag[i] == -1) flag[i] = 0;
    printf("ROW:");
    for (int i = 1; i <= a; i++) if (flag[i]) printf(" %d", i);
    printf("\nCOLUMN:");
    for (int i = a + 1; i <= a + b; i++) if (flag[i]) printf(" %d", i - a);
    printf("\n");
  }
}solve;

int main()
{
  while (scanf("%d%d%d", &n, &m, &k) != EOF)
  {
    solve.clear(n + m + 1);
    for (int i = 1; i <= n; i++) solve.AddEdge(0, i, 1);
    for (int i = 1; i <= m; i++) solve.AddEdge(n + i, n + m + 1, 1);
    for (int i = 1; i <= n; i++)
    {
      scanf("%s", s + 1);
      for (int j = 1; j <= m; j++)
      {
        if (s[j] == '1') solve.AddEdge(i, n + j, 1);
      }
    }
    if ((ans = solve.dinic(0, n + m + 1)) > k) printf("NOT ENOUGH TANK\n");
    else printf("%d\n", ans), solve.find(n, m);
  }
  return 0;
}