锐客网

  1. 首页 > it技术 > >

2019ICPC南昌|2019ICPC南昌 B.A Funny Bipartite Graph（状压dp）

题意： 给定二分图，左半部和右半部各n个点，
给定n*n的01矩阵，如果a(i,j)=1说明左半部的点i与右半部的点j有边。
同时保证i与j有边，当且仅当i<=j，即i>j时一定没边。
还保证每个点的度数>=1且<=3。
现在要求你选出一些边，讲边的两端点选中，要求满足：
1.右半部所有点都被选中
2.给定n*n的01矩阵，如果a(i,j)=1说明左半部的点i和左半部的点j不能同时选择，要求不发生冲突
3.左半部每个点有一个代价M(i)，如果选中了点i，那么代价就是M点i的度数，要求整个图的代价最小。
输出合法的最小代价，如果无解输出-1
【2019ICPC南昌|2019ICPC南昌 B.A Funny Bipartite Graph（状压dp）】数据范围：n<=18，M(i)<=100
解法：

因为点的数量很小，考虑状压dpd[i][ls][rs]表示考虑左边前i个点,左边状态ls,右边状态rs的最小代价 发现ls和rs都是2^n的,数组开不下.题目给出只有i<=j的时候,i才可能向j连边. 那么考虑完左边前i个点后: 1.左边的后n-i个点一定未被选， 2.右边的前i个点一定已经被选了(如果没被选之后也不可能被选,那么就是非法状态),因此:只需要存储左边前i个点的状态和右边后n-i个点的状态 恰好可以用n位二进制数的前i位和后n-i位存储.令d[i][j]表示枚举到i,ls|rs为j的最小合法代价(此时前i-1个点已经合法) 枚举点i的边进行更新即可 考虑左边第i个点的时候,只有当右边第i个点被选上才能进行转移 (因为要保证右边前i个点被选上)ps: 得用scanf参考: https://blog.csdn.net/qq_43202683/article/details/104100695 https://blog.csdn.net/rzo_kqp_orz/article/details/103996351

code：
//https://nanti.jisuanke.com/t/42577 #include using namespace std; const int maxm=20; vectorg[20]; int d[20][1<<20]; int ban[20]; int val[20]; char s[20]; int n; void solve(){ scanf("%d",&n); for(int i=0; i>i&1){//如果右半部第i位已经有了,那么左半部可以不选第i位 d[i+1][j^(1<>k&1)cost*=val[i],es|=(1<>i&1))continue; //没选上右半部第i个点,不合法 d[i+1][ls|es]=min(d[i+1][ls|es],d[i][j]+cost); } } } int ans=1e9; for(int i=0; i<(1<

    推荐阅读


    上一篇：单链表的增删改查

    下一篇：map与xml之间的相互转换