二分图匹配裸题

典型例题

#include<bits/stdc++.h>
using namespace std;
constexpr const int MAXVAL = 505;


int k, m, n;
int couples[MAXVAL][MAXVAL];
int girls[MAXVAL];
int visited[MAXVAL];



int find(int x)
{
int i;
for (i = 1; i <= m; ++i)
{
    if(couples[x][i]==1 && visited[i]==0)
    {
        visited[i] = 1;
        if(girls[i]==0 || find(girls[i]))
        {
            girls[i] = x; return 1;
        }

    }
}

    return 0;
}



int solve()
{
  int ans = 0;
  int i = 0;
  memset(girls, 0, sizeof(girls));
  for (i = 1; i <= n; ++i)
  {
      memset(visited, 0, sizeof(visited));
      if(find(i) == 1) ans = ans + 1;
  }

  return ans;
}


int main(int argc, char const *argv[])
{
    /* code */
    int i;
    int a,b;
    while(cin>>k && k)
    {
        cin>>m>>n;
        memset(couples,0,sizeof(couples));
        for (i = 1; i <=k; ++i)
        {
            /* code */
            cin>>a>>b;
            couples[b][a] = 1;
        }
        cout<<solve()<<endl;
    }

    return 0;
}

理解

BGM算法本质上是递归的算法，其中对每个男生，都会考虑全部女生，这点有点像BootStrap算法。

关于未知行数数据读取方式

参考文章

今天碰到未知输入数量的情况，对C++来说，有点麻烦。而且要想和基本形式一致，还需要采用映射的方式把女生ID映射为从1开始

#include<bits/stdc++.h>
using namespace std;
constexpr const int MAXVAL = 505;

int m = 0, n = 0;
int girls[MAXVAL];
int girls_map_id[MAXVAL];

int main(int argc, char const *argv[])
{
    /* code */
    string S=""; getline(cin,S);
    cout<<"S "<<S<<endl;
    int l=S.size(), base = 0;
    for(int i=0;i<l;i++)
    {
        if(S[i]==' ')
        {
            girls[++m]=base;
            girls_map_id[base] = m;
            base=0;
        }
        else base = base*10+S[i]-'0';
    }
    girls[++m] = base; girls_map_id[base] = m;

    for (int i = 1; i < m; ++i)
    {
        cout<<"girl "<<girls[i]<<' ';
    }

    return 0;
}

关于python复杂排序问题

编程时候经常会遇到复杂的排序情况，之前没有好好总结过，这里总结一下

参考文章
参考文章

from operator import itemgetter

alist = [( '1' , '5' , '1' ), ( '2' , '4' , '1' ),
        ( '3' , '3' , '3' ), ( '4' , '2' , '3' ),
         ( '5' , '1' , '2' )]

# 多级排序，先按照第3个元素排序，然后按照第2个元素排序：

#字典序
print (sorted(alist, key = itemgetter(2,1), reverse = False))
# 转化为整数 单级排序
print (sorted(alist, key = lambda x: int(itemgetter(1)(x)), reverse = False))
# 全部转化为整数
print (sorted(alist, key = lambda x: list(map(int,itemgetter(2 , 1)(x))), reverse = False))
#比较直接的方式
print (sorted(alist, key = lambda x:(int(x[2]), int(x[1])), reverse = False))


blist = {"abcd123_c10000":4,"abcd12_c33":3,"abcd23_c100":2,"abcd21_c9999":1}

# 字典按值排序
print(dict(sorted(blist.items(),  key=lambda x:x[1] ,reverse=False)))
# 字典按键排序
print(dict(sorted(blist.items(),  key=lambda x:x[0] ,reverse=False)))
#按部分的分割字符串排序
print(dict(sorted(blist.items(),  key=lambda x:(int(x[0].split('_c')[1]),x[0].split('_c')[0]) ,reverse=False)))

总结

今天虽然只做出了两道题，但是第一道题我一边就写对了，没有调试，还是很开心。写程序的时候还是要小心，今天第二题我用C++写好了，但是不知咋滴有问题，本地调试发现程序里有输入，但是运行时候没输入数据就结束了。我把程序全部删掉，只剩个main，和输入部分，还是这样，真是玄学，我服了。考试来不及找错误，谁知道哪里错了。赶紧用python又写了一边，过了，但是浪费了好多时间啊。
第三题做过原题（事后才知道，基本忘完了），但是还是没想出来，只想着暴力出奇迹。明显超时了。第四题一开始的以为是贪心，我理解的题意是输入的是每个人的意向，按照意向最少的优先，排个序。
后来发现题目给的直接是双方都有意思的组合，也没啥思路。
总结下来就是，题目要读清楚，不要慌。还有就是写程序一定要细心，最好用本地文本编辑器，有语法检测，有时候写程序会出现莫名奇妙的问题，防不胜防。还有，再次强调的是，理解出题人意图，不要傻傻的暴力破解。