題解

• 首先先轉換題目,就是n個工人和n臺機器,轉換為二分圖模型,左右兩點有邊當且僅當該人會該機器
• 無論哪種情況所有機器都有人操作,而且所有人都有事干,也就是每一個極大匹配都是完美匹配
• 然后有結論為任意一個極大匹配都是完美匹配當且僅當二分圖中每一個聯通塊都是左右點數相同的完全二分圖
• 證明如下:
• 然后我們回到問題本身,那么記錄一開始每個聯通塊左右點數為(xi,yi),現在的問題就是將(xi,yi)分成若干個集合,然后要滿足Σi∈s(xi)=Σi∈s(yi)
• 考慮狀壓dp,設f[s][i]為集合中s已經劃分出Σx=i的最小代價,至于轉移的話,枚舉x從f[s]轉移到f[s∪{x}]
• 然后就可以過這道題了

代碼

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 const int inf=168430090,N=40,M=223321; 7 struct data{int x,y,num;}p[N]; 8 struct edge{int to,from;}e[N*N*2]; 9 int n,m,cnt,tot,sum,g[M][N],f[M][N],l[N],s[N],head[N*2];10 char S[N]; bool bz[N*2],pd[M];11 void insert(int x,int y)12 {13     e[++cnt].to=y,e[cnt].from=head[x],head[x]=cnt;14     e[++cnt].to=x,e[cnt].from=head[y],head[y]=cnt;15 }16 void dfs(int x)17 {18     if (x<=n) p[tot].x++; else p[tot].y++; bz[x]=1;19     for (int i=head[x];i;i=e[i].from) if (!bz[e[i].to]) dfs(e[i].to);20 }21 bool cmp(data a,data b) { return a.x==b.x?a.y<b.y:a.x<b.x; } 22 void check(int x)23 {24     int r=x,a=0,b=0;25     for (int i=m;i>=1;i--) while (r>=l[i]) g[x][i]++,a+=p[i].x,b+=p[i].y,r-=l[i];26     pd[x]=(a==b);27 }28 int main()29 {30     freopen("factory.in","r",stdin),freopen("factory.out","w",stdout),scanf("%d",&n);31     for (int i=1;i<=n;i++)32     {33         scanf("%s",S+1);34         for (int j=1;j<=n;j++) if (S[j]=='1') sum++,insert(i,j+n);35     }36     for (int i=1;i<=n;i++) if (!bz[i+n]) tot++,dfs(i+n);37     for (int i=1;i<=n;i++) if (!bz[i]) p[++tot]=(data){1,0,0};38     sort(p+1,p+tot+1,cmp),m=p[1].num=1;39     for (int i=2;i<=tot;i++) if (p[i].x!=p[i-1].x||p[i].y!=p[i-1].y) p[++m]=(data){p[i].x,p[i].y,1}; else p[m].num++;40     l[1]=1,s[1]=p[1].num; for (int i=2;i<=m;i++) l[i]=s[i-1]+1,s[i]=s[i-1]+l[i]*p[i].num;41     memset(f,10,sizeof(f)),f[0][0]=0;42     for (int i=1;i<=m;i++) f[l[i]][p[i].x]=0;43     for (int i=1;i<=s[m];i++) check(i);44     for (int i=0;i<=s[m];i++) for (int j=1;j<=m;j++) if (p[j].num!=g[i][j]) for (int k=0;k<=n;k++) if (f[i][k]!=inf)45     { 46         f[i+l[j]][k+p[j].x]=min(f[i][k],f[i+l[j]][k+p[j].x]);47         if (pd[i+l[j]]) f[i+l[j]][0]=min(f[i+l[j]][0],f[i+l[j]][k+p[j].x]+(k+p[j].x)*(k+p[j].x));48     }49     printf("%d",f[s[m]][0]-sum);50 }