hdu2819二分图匹配

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

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=+,maxn=+,inf=0x3f3f3f3f;

int color[N],n;

bool used[N],ok[N][N];

bool match(int x)

{

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

    {

        if(ok[x][i]&&!used[i])

        {

            used[i]=;

            if(color[i]==||match(color[i]))

            {

                color[i]=x;

                return ;

            }

        }

    }

    return ;

}

int solve()

{

    int ans=;

    memset(color,,sizeof color);

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

    {

        memset(used,,sizeof used);

        ans+=match(i);

    }

    return ans;

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    while(cin>>n){

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

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

                cin>>ok[i][j];

        if(solve()!=n)cout<<-<<endl;

        else

        {

 //           for(int i=1;i<=n;i++)cout<<color[i]<<endl;

            memset(used,,sizeof used);

            queue<pair<int,int> >q;

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

            {

                if(i==color[i])continue;

                for(int j=i+;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 ;

}

巴特西

hdu2819二分图匹配

最新文章

热门文章