hdu2819二分图匹配-白红宇的个人博客

hdu2819二分图匹配

发布日期：2021-06-24 04:57:46 浏览次数：9 分类：技术文章

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

Given an N*N matrix with each entry equal to 0 or 1. You can swap any two rows or any two columns. Can you find a way to make all the diagonal entries equal to 1?

InputThere are several test cases in the input. The first line of each test case is an integer N (1 <= N <= 100). Then N lines follow, each contains N numbers (0 or 1), separating by space, indicating the N*N matrix.OutputFor each test case, the first line contain the number of swaps M. Then M lines follow, whose format is “R a b” or “C a b”, indicating swapping the row a and row b, or swapping the column a and column b. (1 <= a, b <= N). Any correct answer will be accepted, but M should be more than 1000.

If it is impossible to make all the diagonal entries equal to 1, output only one one containing “-1”.

Sample Input

20 11 021 01 0

Sample Output

1R 1 2-1 题意：给一个只有0 1的矩阵，是否能通过交换两行或者两列使对角线全为1 题解：二分图匹配x和y，输出方法是关键，两遍循环取对应的xy不相同的进行交换记录交换的行或者列（由矩阵知识可知行和列交换一种就行了） 刚开始因为but M should be more than 1000. 这句话我非要作死输出1000个，话说题目能不能不要瞎写啊！！！

#include#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define pi acos(-1)#define ll long long#define mod 1000000007using namespace std;const int N=100+5,maxn=100000+5,inf=0x3f3f3f3f;int color[N],n;bool used[N],ok[N][N];bool match(int x){ for(int i=1;i<=n;i++) { if(ok[x][i]&&!used[i]) { used[i]=1; if(color[i]==0||match(color[i])) { color[i]=x; return 1; } } } return 0;}int solve(){ int ans=0; memset(color,0,sizeof color); for(int i=1;i<=n;i++) { memset(used,0,sizeof used); ans+=match(i); } return ans;}int main(){ ios::sync_with_stdio(false); cin.tie(0); while(cin>>n){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>ok[i][j]; if(solve()!=n)cout<<-1<
                 
                   >q; for(int i=1;i<=n;i++) { if(i==color[i])continue; for(int j=i+1;j<=n;j++) { if(j==color[j])continue; if(i==color[j]) { q.push(make_pair(i,j)); swap(color[i],color[j]); } } } cout<
                  
                   <

View Code

转载于:https://www.cnblogs.com/acjiumeng/p/6740168.html

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

上一篇：Educational Codeforces Round 22E

下一篇：phpcms网站迁移无法更新内容提示Table 'led_com.lz_' doesn't exist的解决方法

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章