有创意的婚纱网站模板下载,库尔勒网站建设,wordpress 侧边栏代码,56m做图片视频的网站是什么B - A Funny Bipartite Graph
题意#xff1a;
一个二分图#xff0c;左右各有n个点#xff0c;左边第i个点有一个属性mi#xff0c;它在一个图中的价值为midi,其中di为它在图中的度数(特殊的#xff0c;如果度数为0#xff0c;则价值为0)#xff0c;求一个该二分图的…B - A Funny Bipartite Graph
题意
一个二分图左右各有n个点左边第i个点有一个属性mi它在一个图中的价值为midi,其中di为它在图中的度数(特殊的如果度数为0则价值为0)求一个该二分图的子图使得右边的每个点度数都不为0且总价值最小输出最小价值。如果无解输出−1 有若干个限制条件(i,j)表示子图中左边的点i和j不能同时存在 保证 原二分图中左边的每个点度数在[1,3]之间。 左边的i点和右边的j点连线当且仅当i ≤ j n18 mi100
题解
参考题解 文章1 文章2 这个题的思路非常妙 首先根据数据范围确定方法为状压dp 我们既要维护左侧的点也有维护右侧的点两侧都是n我们都用二进制取枚举那么复杂度就是n * 22n,这样肯定不行要先办法优化 注意题目中有说左侧的i选右侧的j当且仅当ij,也就是说当我们考虑左侧的第i个点时左侧的后n-i个还没选右侧的前i个点必须全选(不然往后再也选不了)也就是说左侧的后n-i位和右侧的前i位都没啥用所有我们可以将左侧的前i位和右侧的后n-i位拼成一起这样2n就可以存下复杂度就是O(n*2n) 这波操作就相当于计组里面将32 位整数乘除法它把乘数和结果同时存在了一个 64 位整数上 妙哉妙哉 思路很难代码也很难。。代码之后更新
代码:
#includebits/stdc.h
#define ll long long
using namespace std;
const int inf 0x3f3f3f3f;
int dp[2][118];
int val[20], ban[20];
vectorint g[20];
char s[20];
int n;
void init(){scanf(%d, n);for(int i 0; i n; i) g[i].clear();for(int i 0; i n; i) {scanf(%s, s);for(int j 0; j n; j) if(s[j] 1) g[i].push_back(j);}for(int i 0; i n; i) {scanf(%s, s); ban[i] 0;for(int j 0; j i; j) if(s[j] 1) ban[i] | (1j);}for(int i 0; i n; i) scanf(%d, val[i]);
}
int sol(){int cur 0, nxt 1;memset(dp, 0x3f, sizeof dp);dp[cur][0] 0;for(int i 0; i n; i){for(int mask 0; mask (1n); mask){int lstate mask((1i)-1);int rstate mask((1n)-(1i));if(dp[cur][mask] inf) continue;// dont choose iif(rstatei1) dp[nxt][(mask)^(1i)] min(dp[nxt][(mask)^(1i)], dp[cur][mask]);if(ban[i]lstate) continue;//cant choose ifor(int t 1; t (1g[i].size()); t){int cost 1;int ex 0;for(int j 0; j g[i].size(); j){int v g[i][j];if(tj1) cost * val[i], ex | 1v;}int nstate rstate|ex;if( !(nstatei1) ) continue;int sumstatelstate|nstate;dp[nxt][sumstate] min(dp[nxt][sumstate], dp[cur][mask] cost);}}swap(cur, nxt);memset(dp[nxt], 0x3f, sizeof dp[nxt]);}int ans inf;for(int i 0; i (1n); i) ans min(ans, dp[cur][i]);if(ans inf) return -1;return ans;
}
int main()
{int T;cinT;while(T--){init();coutsol()endl;}
}
