uva1609 Foul Play

思维 创造条件使一轮比赛之后仍满足1号打败至少一半，并剩下至少一个t'

紫书上的思路很清晰
阶段1,3保证黑色至少消灭1半

#include<cstdio>

#include<vector>

using namespace std;

const int maxn =  + ;

char table[maxn][maxn];

int main() {

  int n;

  while(scanf("%d", &n) == ) {

    for(int i = ; i <= n; i++) scanf("%s", table[i]+);

    vector<int> win, lose; // teams that team 1 win/lose against.

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

      if(table[][i] == '') win.push_back(i);

      else lose.push_back(i);

    int nt = n;

    while(nt > ) {

      vector<int> win2, lose2, final; // phase 3/4

      // Phase 1

      for(int i = ; i < lose.size(); i++) {

        int tlose = lose[i];

        bool matched = false;

        for(int j = ; j < win.size(); j++) {

          int& twin = win[j];

          if(twin >  && table[twin][tlose] == '') {  //尽量通过配对消灭黑

            printf("%d %d\n", twin, tlose);

            win2.push_back(twin); // go to the next round

            twin = ; // not available   本轮已经配对

            matched = true;

            break;

          }

        }

        if(!matched) final.push_back(tlose); // to phase 3/4

      }

      // Phase 2

      bool first = true;

      for(int i = ; i < win.size(); i++) {

        int twin = win[i];

        if(twin > ) {

          if(first) { printf("1 %d\n", twin);first = false; }

          else final.push_back(twin);

        }

      }

      // Phase 3/4

      for(int i = ; i < final.size(); i += ) {    //3,4阶段可以一起处理

        printf("%d %d\n", final[i], final[i+]);

        int keep = final[i];

        if(table[final[i+]][keep] == '') keep = final[i+];

        if(table[][keep] == '') win2.push_back(keep);

        else lose2.push_back(keep);

      }

      win = win2;

      lose = lose2;

      nt >>= ;

    }

  }

  return ;

}