【解题思路】
考虑拆点,得到一个二分图:左边点<i,j>表示第i个技师按顺序第j辆修的车,右边点k表示第k个车主,连接左右的边表示第k个车主可能成为第i个技师的第j个客户。
因为是二分图,所以直接跑KM即可,复杂度O(n3m);或者考虑费用流,左图都和源点连边,右图都和汇点连边,容费均为1,跑个流即可,复杂度O(松)。
【参考代码】
费用流实现:
1 #pragma GCC optimize(2) 2 #include3 #include 4 #define REP(i,low,high) for(register int i=(low);i<=(high);i++) 5 #define INF 0x7f7f7f7f 6 using namespace std; 7 template inline bool getmin(T &tar,const T &pat) { return pat