题目大意

工厂内每个人只会操作一些机器。

他们会以随机的顺序来，每次选任意一台机器来操作。

一台机器只能由一个工人来操作。

可以花费一的代价来使某个工人学会一种机器。

问花费最少的代价，使得在所有的情况下每个人都能操纵一台机器。

正解

这题可以转化成个二分图。而答案一定满足：==所有联通块都是个完全二分图==。

我们要用最少的代价来造出这样的二分图。

预处理出所有的联通块，每个联通块用\((x,y)\)表示，意味着左边有\(x\)个，右边有\(y\)个。

于是就有了下面这个状压DP：\(f_{S,i}\)表示\(S\)集中的联通块都被使用了，其中完成了的联通块的\(x\)之和为\(i\)的最小边数。

等等，这个状态会不会存不下？

实际上，对于相同的\((x,y)\)，我们只关心数量，所以可以进一步压缩。然后状态的数量就变得少了很多。

最后的答案记得要减去原来就有的边数。

代码

using namespace std;#include 
    
     #include 
     
      #include 
      
       #define N 33inline void update(int &x,int y){x>y?x=y:0;}int n;char can[N][N];bool vis[N][2];int cntl,cntr,have;void find(int x,bool k){    vis[x][k]=1;    if (k==0){        cntl++;        for (int i=1;i<=n;++i)            if (can[x][i]=='1' && !vis[i][1])                find(i,1);    }    else{        cntr++;        for (int i=1;i<=n;++i)            if (can[i][x]=='1' && !vis[i][0])                find(i,0);    }}int sc[N][N];struct State{    int x,y;    int num;} lis[N];int m;int pro[N];int chose[N];int f[200000][N];void dfs(int k,int s,int x,int y){    if (k>m){        if (s==0)            f[0][0]=0;        for (int j=0;j