hdu 2819 二分图匹配

约定不等于承诺〃 2022-08-02 16:58 88阅读 0赞

总共wa了十几发，，，开始以为某一行或者某一列上没有1，全是0就输出-1，结果杯具了。。1 1 1 ， 0 1 0， 0 1 0例如这个例子也要输出-1。。。

改了之后在二分图匹配的时候判断，dfs给每一行匹配，如果这行匹配不上，那么就说明没办法做到使对角线全是1。

输出的时候又WA了好几发，开始以为把结果简单的输出就行了，后来去网上查了查，想到交换了这两行之后会造成影响波及后面的匹配，，

比如4跟1交换了，后面有2跟1匹配，输出的时候应该改为2跟4交换。。

//hdu2819
    //二分图匹配 行列匹配
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    const int N=102;
    vector<int> v[N];
    int maze[N][N];
    int vis[N];
    int temp;
    int match[N];
    
    
    bool dfs(int x)
    {
        for(int i=0;i<(int)v[x].size();i++)
        {
            int t=v[x][i];
            if(vis[t]==0)
            {
                vis[t]=1;
                if(match[t]==-1 || dfs(match[t]))
                {
                    match[t]=x;
                    return 1;
                }
            }
        }
        return 0;
    }
    
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            for(int i=0;i<=n;i++)v[i].clear();
            
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    maze[i][j]=in();
    
            for(int j=1;j<=n;j++)       //建图，第i行能匹配在第i列有1的那些行
                for(int i=1;i<=n;i++)
                    if(maze[i][j]) v[j].push_back(i);
                
            
            mem(vis,0);
            mem(match,-1);
            bool ok=1;
            for(int i=1;i<=n;i++)
            {
                mem(vis,0);
                if(!dfs(i))ok=0; //不符合要求
            }
            if(!ok)
            {
                puts("-1");
                continue;
            }
           queue<pii> q;
           int i,j;
           for( i=1;i<=n;i++)
           {
               for( j=1;j<=n;j++)
               {
                   if(match[j]==i)break;
               }
               if(j!=i)
               {
                   q.push(pii(i,j));
                   swap(match[i],match[j]);//修改交换之后的影响，
                            //比如4跟1交换了，后面有2跟1匹配，输出的时候应该改为2跟4交换
               }
    
           }
    
           printf("%d\n",q.size());
           while(!q.empty())
           {
               pii now = q.front();
               q.pop();
               printf("R %d %d\n",now.first,now.second);
           }
    
        }
        return 0;
    }