なぜ二分図の最大二分整合数が最小点オーバーライド数に等しいのか

md、昨夜のtc 500 ptができなかったなんて、アルゴリズムについて深く理解していなかった...2333333、もう話さない.の
私が言いたいのはここに詳しい文章がありますが、ちょっと詳しく感じました.http://www.matrix67.com/blog/archives/116
博文によると、ハンガリーのアルゴリズムを1回完成した後、右側の未選択点から増広路を探し始めた(明らかに見つからない).この過程で1つの交差木が見つかり、起点はすべて未一致点で、終点はすべて一致点で、次の結論があった.
左に検索されたポイントと右にアクセスされていないポイントが、私たちが探している最も小さな点で覆われているポイントセットです.
以下に二つのものを証明する
1:これらの点の数はM(最大一致数)
2:これらの点はすべてのエッジを上書きできます.
3:これらの点は最も少ない条件を満たす点です(1を証明して、これは自然に証明して、一致する辺がM本あるため、これらの辺をカバーするのは少なくともM個の点が必要です)
証明1:選択したポイントセットの各ポイントは一致するエッジに対応し、同じ一致するエッジに属する2つのポイントはありません.
証明2:すべてのエッジは選択したポイントセットの「魔の爪」から逃れられません.エッジを分類します.マッチングエッジ、非マッチングエッジ
非一致エッジは2つに分けられます
(1:左はマッチングポイント、右は非マッチングポイントで、このエッジの左端はすでに私たちが選んだポイントセットのポイントなので、このエッジは制御されているに違いありません.
(2:左は非整合点、右は整合点、この辺の右端点は明らかに到達できない.右のある未アクセス点からこの右端点に到達し、それから左の非整合点に着くと、交錯木の首尾が非整合辺になるため、拡張路が見つかり、矛盾するため、この辺の右端点はすべて未アクセス点であり、上書き点に選択されるセットなので、この辺も制御されています
例題:
50*50のメッシュをあげます.メッシュには3種類あります.「O」「X」
空き地、すなわち「.」にXを置くことができ、Oの周りの空き地がXされると、このOは「.」になり、最も多くのものを得ることができるように適切な戦略を取らなければなりません.
明らかに私たちはすべてのOが「.」になり、そしてすべての「.」が変わらないことを望んでいます.このような総数がn+mであると仮定します.
しかし、明らかにできないことが多いので、条件を満たすことができないOを最小限に抑え、最も多いOと「」の総量を残す必要があります.
実は最大点の独立集の問題で、1つのOが独立する時、彼の周囲はいかなる“.”がなくて、天然にテーマの要求を満たしました.
srm 594  level2

#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <ctime>
using namespace std;

class FoxAndGo3
{
public: 
    int maxEmptyCells(vector <string> board);
    
    
// BEGIN CUT HERE
	public:
	void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }
	private:
	template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
	void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
	void test_case_0() { string Arr0[] = {"o.o",
 ".o.",
 "o.o"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 5; verify_case(0, Arg1, maxEmptyCells(Arg0)); }
	void test_case_1() { string Arr0[] = {"...",
 ".o.",
 "..."}
; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 8; verify_case(1, Arg1, maxEmptyCells(Arg0)); }
	void test_case_2() { string Arr0[] = {"xxxxx",
 "xxoxx",
 "xo.ox",
 "xxoxx",
 "xxxxx"}
; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 4; verify_case(2, Arg1, maxEmptyCells(Arg0)); }
	void test_case_3() { string Arr0[] = {".xox.",
 ".o.ox",
 "x.o.o",
 "ox.ox",
 ".ox.."}
 ; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 12; verify_case(3, Arg1, maxEmptyCells(Arg0)); }
	void test_case_4() { string Arr0[] = {"o.o.o",
 ".ox..",
 "oxxxo",
 "..x..",
 "o.o.o"}
; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 12; verify_case(4, Arg1, maxEmptyCells(Arg0)); }
	void test_case_5() { string Arr0[] = {"...",
 "...",
 "..."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 9; verify_case(5, Arg1, maxEmptyCells(Arg0)); }

// END CUT HERE

};

// BEGIN CUT HERE
int main()
{
    FoxAndGo3 ___test;
    ___test.run_test(-1);
    return 0;
}
// END CUT HERE
int n1,n2;
vector<int> g[55*55];
int id[55][55];
bool vis[55*55];
int match[55*55];
bool dfs(int u)
{
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if(vis[v]) continue;
        vis[v] = true;
        if(match[v] == -1 || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}
int dx[]={
    0,0,1,-1
};
int dy[]={
    1,-1,0,0
};
int FoxAndGo3::maxEmptyCells(vector <string> board)
{
  int n = board.size(),m = board[0].length();
  n1 = 0; n2 = 0;
  for(int i = 0; i < board.size(); i++) {
      for(int j = 0; j < board[i].length(); j++) {
          if(board[i][j] == '.') {
              n1++;
              id[i][j] = n1;
          }
      }
  }
  for(int i = 1; i <= n1; i++) g[i].clear();
  for(int i = 0; i < board.size(); i++) {
      for(int j = 0; j < board[i].length(); j++) {
          if(board[i][j] == 'o') {
              n2++;
              for(int k = 0; k < 4; k++) {
                  int x = i + dx[k];
                  int y = j + dy[k];
                  if(x >= 0 && x < n && y >=0 && y < m && board[x][y]=='.') {
                      g[id[x][y]].push_back(n2);
                  }
              }
          } 
      }
  }
  int ret = n1 + n2;
  for(int i = 1; i <= n2; i++) match[i]=-1;
  for(int i = 1; i <= n1; i++) {
      for(int j = 1; j <= n2; j++) vis[j]=false;
      if(dfs(i)) ret--;
  }
  return ret;
}