@[toc]

I. Error Correction

题目大意

给你 N 个长度相同的字符串，问你最多选多少个可以使他们两两之间不能通过交换一对字符串而相等，
比如说 abc和acb就可以通过第二个字符串交换cb的位置就相等了；

解题思路

我们可以发现字符串abc满足这样的条件
a 可以转换成 c
c 可以转换成 b
但是 a 不可以转换成 b
因此这个就是一个二分图的最大独立集问题，
二分图的最大独立集=顶点个数- 最大匹配数/2

代码

 #include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0)
#define ll long long
const int M=1000;
bool  used[M];//用于标记是否用过 
int link[M];//这个点连接的是哪个点 
vector<int>ve[M];//存图 
string s[M];
int un,vn;//un vn两遍各有几个点 
//********************began***********
bool dfs(int u)
{
    for(int v:ve[u])
    {
        if(!used[v])
        {
            used[v]=1;
            if(0==link[v]||dfs(link[v]))
            {
                link[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
void hungary()
{
    int sum=0;
    for(int u=1;u<=vn;u++)
    {
        memset(used,0,sizeof used);
        if(dfs(u)) sum++;
    }
    cout<<(vn-sum/2)<<"\n";
}
//*************************end**************
int main()
{
    int n;cin>>n;
    un=vn=n;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
    }
    int f=0;
    int l=s[1].length();
//        构造二分图 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            f=0;
            for(int k=0;k<l;k++)
            {
                if(s[i][k]!=s[j][k]) f++;
            }
            if(f==2){
                ve[i].push_back(j);
            }
        }
    }
//************************    
    hungary();
    return 0;
}