做推送用的网站,制作wordpress静态首页,怎么设计网页背景图片,安仁做网站正题 题目大意
有盟友和情敌关系#xff0c;情敌的情敌是朋友之类的规则#xff0c;然后如果一个人和111的关系已经确定#xff0c;以后都不会有任何影响#xff0c;然后求一个序列#xff0c;要求111的盟友最大。 解题思路
定义与111直接连边的是AAA类点#xff0c;不…正题 题目大意
有盟友和情敌关系情敌的情敌是朋友之类的规则然后如果一个人和111的关系已经确定以后都不会有任何影响然后求一个序列要求111的盟友最大。 解题思路
定义与111直接连边的是AAA类点不与111直接连边但与与AAA直接连边的是BBB类点 我们发现如果已经确定某些BBB类点我们发现对于AAA类点的选择顺序并不重要所以我们可以用状压dpdpdp用0/10/10/1表示一个BBB类点的关系是否确定。这样时间复杂度O(2B)O(2^B)O(2B)
然后如果我们已经知道AAA类点是否选择我们可以发现我们也不需要知道前面的序列所以我们可以用状压dpdpdp用0/10/10/1表示一个点是否选择。这样的时间复杂度为O(2A)O(2^A)O(2A)
然后我们每次选择一个最小的时间复杂度O(2min{A,B})O(2^{min\{A,B\}})O(2min{A,B})那么因为有AB≤nAB\leq nAB≤n所以有min{A,B}≤n2min\{A,B\}\leq \frac{n}{2}min{A,B}≤2n codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N55;
ll n,m,v[N][N],id[N],f[123];
ll con[N],dev[N];
ll cnt1,cnt2,ans;
int main()
{freopen(friends.in,r,stdin);freopen(friends.out,w,stdout);scanf(%lld%lld,n,m);memset(v,-1,sizeof(v));for(ll i1;im;i){ll x,y,opt;scanf(%lld%lld%lld,x,y,opt);v[x][y]opt;v[y][x]opt;}for(ll i2;in;i){if(v[1][i]-1) continue;id[i]cnt1;ansv[1][i]^1; for(ll j2;jn;j){if(v[1][j]-1v[i][j]!-1){if(!id[j]) id[j]cnt2;con[id[i]-1]|1id[j]-1;dev[id[i]-1]|(ll)((v[1][i]^v[i][j]^1)id[j]-1);}}}if(cnt1cnt2){ll MS1cnt1;memset(f,0xcf,sizeof(f));f[0]0;for(ll i0;iMS;i){if(f[i]0) continue;ll k0;for(ll j0;jcnt1;j) if(i(1j)) k|con[j];for(ll j0;jcnt1;j)if(!(i(1j)))f[i|(1j)]max(f[i|(1j)],f[i]__builtin_popcountll(dev[j](~k)));}ansf[MS-1];}else{ll MS1cnt2;memset(f,0xcf,sizeof(f));f[0]0;for(ll i0;iMS;i){if(f[i]0) continue;ll k0;for(ll j0;jcnt1;j)if((i|con[j])!i)f[i|con[j]]max(f[i|con[j]],f[i]__builtin_popcountll(dev[j](~i)));}ansf[MS-1];}printf(%lld,ans);
}
