hdu 2819 Swap [二分图匹配]

这道题其实是一道比较简单的题，但是我之前WA了一个晚上，简直不敢相信，当然也是我太想当然了，其实之前的写法有很大的问题，小数据就测不出来问题，所以反思一下，还是要谦虚，仔细啊。。

这个题就是给你一个N*N的一个由0和1组成的图，然后让你通过交换行和列把他编程斜右下对角线上的元素都是1的情况，问你能不能实现，如果能，输出交换路径。

根据题意我们发现，如果我们要满足斜对角线都是1的情况，至少要满足每一行都有一个1 并且每一列都有一个1( 因为假设有一行没有1，那么无论怎么交换列，这一行都不会有1，无论怎么交换行，这行0 都存在，所以必须要有1，这个列也同理，很容易看出来)，那么现在我们发现，也就是说现在有N行 N列，保证每行每列都有一个1，这就有二分图的模型了，所以这时候我们只要把每一行上在第几列出现1连一条线就好了。根据这个图求一个最大匹配，如果匹配数恰好为N的话，那么就成立。

输出路径就只要不断的交换行，一行一行的调整好就行了。
//虽然说起来这么容易，我就是在这里想当然的错了一个晚上

先贴一份AC代码

#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n;
const int maxn=1500;
vector<int>G[maxn];
int match[maxn];
bool used[maxn];
int a[maxn][maxn];
int vis[maxn][3];
//5
//1 0 1 1 0
//1 1 0 0 1
//0 0 0 1 1
//0 1 1 1 1
//1 1 0 1 0
void add_edge(int u,int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}
bool dfs(int v)
{
    used[v]=true;
    for(int i=0; i<G[v].size(); i++)
    {
        int u=G[v][i];
        int w=match[u];
        if(w<0||!used[w]&&dfs(w))
        {
            match[v]=u;
            match[u]=v;
            return true;
        }
    }
    return false;
}
int bipartite_matching()
{
    int res=0;
    memset(match,-1,sizeof(match));
    for(int v=0; v<maxn; v++)
    {
        if(match[v]<0)
        {
            memset(used,0,sizeof(used));
            if(dfs(v))
            {
                res++;
            }
        }
    }
    return res;
}
int change()
{
    int cnt=0;
    for(int i=1; i<=n; i++)
    {
        if(match[i]==i+n)continue;

        for(int j=i+1;j<=n;j++)
          if(match[j]==i+n)
          {
            match[j]=match[i];
            cnt++;
            vis[cnt][1]=i;
            vis[cnt][2]=j;

        }
    }
    return cnt;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(vis,0,sizeof(vis));
        for(int i=0; i<maxn; i++)
        {
            G[i].clear();
        }
        memset(a,0,sizeof(a));
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(a[i][j]==1)
                {
                    add_edge(i,n+j);

                }
            }
        }
        int ans=bipartite_matching();
// for(int i=1; i<=n; i++)
// {
// printf("%d ",match[i]-n);
// if(i%5==0) cout<<endl;
// }
// cout<<endl;
        if(ans!=n) printf("-1\n");
        else
        {
            int num=change();
            printf("%d\n",num);
            for(int i=1; i<=num; i++)
            {
                printf("R %d %d\n",vis[i][1],vis[i][2]);
            }
        }
    }
    return 0;
}

当然我之前对与change这个函数并不是这么写的，我以为只要发现i对应的行把他移到该移的位置，但是我忘记了，后面交换回去的可能顺序不对，所以一直用O（n）的错误方法，试图解决n^2的问题。实在惭愧。

int change()
{
    int cnt=0;
    for(int i=1; i<=n; i++)
    {
        if(match[i]!=i+n)
        {
            int t=match[i]-n;
            int k=match[t];
            match[i]=match[t];
            match[i]=k;
            cnt++;
            vis[cnt][1]=i;
            vis[cnt][2]=t;
            //cout<<i<<" "<<vis[cnt][1]<<" "<<vis[cnt][2]<<endl;
        }
    }
    return cnt;
}