这道题用构造法， 就是自己依据题目想出一种可以得到解的方法， 没有什么规律可言， 只能根据题目本身来思考。
这道题的构造法比较复杂， 不知道刘汝佳是怎么想出来的， 我想的话肯定想不到。
具体思路紫书上讲得非常清楚了， 就不讲了。代码有详细注释
#include<cstdio>
#include<vector>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 1123;
char table[MAXN][MAXN];int main()
{int n;while(~scanf("%d", &n)){REP(i, 1, n + 1) scanf("%s", table[i] + 1); //表都是从１开始 vector<int> win, lose; // 先处理１号队能打败和不能打败的队伍 REP(i, 2, n + 1){if(table[1][i] == '1') win.push_back(i);else lose.push_back(i);}int nt = n; //队伍的个数 while(nt > 1){vector<int> win2, lose2, final; // win2是下一轮的win，结尾用来更新win的， // lose2同样。final是最后一阶段的REP(i, 0, lose.size()) // 第一阶段配对，尽量干掉１不能干掉的队伍 {int tlose = lose[i];bool matched = false;REP(j, 0, win.size()){int& twin = win[j];if(twin > 0 && table[twin][tlose] == '1'){printf("%d %d\n", twin, tlose);win2.push_back(twin);twin = 0; //表示这支队伍这一轮已经打完了，之后不能再用了 matched = true;break;}}if(!matched) final.push_back(tlose); //多余的黑色队伍留到后面 }bool first = true; //第二阶段，把队伍１和另一支队伍打完，然后剩下的留到最后 REP(i, 0, win.size()){int twin = win[i];if(twin > 0){if(first) printf("1 %d\n", twin), first = false;else final.push_back(twin);}}for(int i = 0; i < final.size(); i += 2) //这里注意因为黑色的队伍是连续加入的，{ //所以一开始是第三阶段，然后之后是第四阶段 printf("%d %d\n", final[i], final[i+1]);int keep = final[i];if(table[final[i+1]][keep] == '1') keep = final[i+1];if(table[1][keep] == '1') win2.push_back(keep);else lose2.push_back(keep);}win = win2; //更新下一轮的 win和 loselose = lose2;nt >>= 1; //队伍个数减半 } }return 0;
}