首页 > 代码库 > hdu2819二分图匹配

hdu2819二分图匹配

2024-09-16 03:08:37   221人阅读

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

2
0 1
1 0
2
1 0
1 0

Sample Output

1
R 1 2
-1
题意：给一个只有0 1的矩阵，是否能通过交换两行或者两列使对角线全为1
题解：二分图匹配x和y，输出方法是关键，两遍循环取对应的xy不相同的进行交换记录交换的行或者列（由矩阵知识可知行和列交换一种就行了）
刚开始因为but M should be more than 1000. 这句话我非要作死输出1000个，话说题目能不能不要瞎写啊！！！
技术分享 
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define ll long long
#define mod 1000000007

using 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<<endl;
        else
        {
 //           for(int i=1;i<=n;i++)cout<<color[i]<<endl;
            memset(used,0,sizeof used);
            queue<pair<int,int> >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<<q.size()<<endl;
            while(!q.empty()){
                cout<<"C "<<q.front().first<<" "<<q.front().second<<endl;
                q.pop();
            }
        }
    }
    return 0;
}
View Code

 

hdu2819二分图匹配


联系
我们