本文共 1804 字，大约阅读时间需要 6 分钟。

题意不难，n*n矩阵有n-1个1，求最少的步数将所有的1交换到主对角线一下，并输出交换序列。这里的交换是整行或者整列进行交换。这题的代码不是我写的，看也并没有完全看明白，对一些看明白的地方我加了注解，先记录下来，哪天回头看的时候可能就显而易见了。

//代码不是我写的，参考别人的，重在学习！#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;int mat[1010][1010];bool fliped[1010];int n;void swapr(int a, int b){	for (int i = 1; i <= n; i++)		swap(mat[a][i], mat[b][i]);}void swapc(int a, int b){	for (int i = 1; i <= n; i++)		swap(mat[i][a], mat[i][b]);}struct Column {	int cnt1;//记录每一列1的个数	bool vis;//标记某列是否被访问过	int now;//现在在第几列	Column(){}//默认的构造函数	Column(int c, int id)	{		vis = false;		cnt1 = c;		now = id;	}}p[1010];int main(){	int x, y,i,j;	cin >> n;	for (i = 1; i < n; i++)	{		cin >> x >> y;		mat[x][y] = 1;	}	for (i = 1; i <= n; i++)	{		int cnt = 0;		for (j = 1; j <= n; j++)		{			if (mat[j][i] == 1)				cnt++;//记录第i列1的个数		}		p[i] = Column(cnt, i);//初始化第i列	}	vector
       
        
          > ret; for (i = 1; i <= n; i++) { int mx = -1, id = -1; for (j = 1; j <= n; j++) { if (p[j].cnt1 > mx && !p[j].vis)//第j列有1并且没有被访问过 { mx = p[j].cnt1; id = j;//每一趟循环下来交换的是1最多的一列 } } p[id].vis = true; if (p[id].now != i) { swapc(p[id].now, i); ret.push_back(make_pair(p[id].now, i));//ret里存储的是列交换操作 for (j = 1; j <= n; j++) { if (p[j].now == i) p[j].now = p[id].now; } } } int now = n;//此时的now标记的是行 vector
         
          
            > ans; for (i = n; i >= 1; i--) { now = n; for (j = n; j > i; j--) if (mat[j][i]) fliped[j] = true;//fliped标记对角线之下某一行是否有1 for (j = 1; j <= i; j++)//j<=i表示对角线之上 { if (mat[j][i])//j<=i表示对角线之上有1的情形 { while (mat[now][i] || fliped[now]) now--;//now最终的位置表示对角线之下为fliped[now]=0也就是第now行没有1并且mat[now][i]=0 swapr(now, j); fliped[now] = true; ans.push_back(make_pair(now, j)); now--; } } } cout << ret.size() + ans.size() << endl; for (i = 0; i < ret.size(); i++) cout << 2<<" "<
           
            << " " << ret[i].second << endl; for (i = 0; i 
           
          
         
        
       
      
     
    
   

转载地址：https://jianzhuwang.blog.csdn.net/article/details/45127419 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！