This recent problem Bank Cooperation, from a codechef contest is solved using bit manipulation in editorial but i think it is solvable by this graph approach too.
All 8 items can be thought as nodes in graph, where the paired up elements will form one component, now in components we cannot take neighbouring nodes, as they can`t be put together.So I found the maximum value that we can take from a component by doing modified dfs, and then added the maximum values of all the components.
I have thought of many cases but cant figure out why its wrong, please help…
My Code
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>gr(8);
bool vs[8];
int A[8];
void dfs(int v,vector<int>& tmp){
if(vs[v]){
return;
}
vs[v] = true;
tmp.pb(v);
for(auto i:gr[v]){
dfs(i,tmp);
}
return;
}
void spdfs(int v, int f, int& s){
if(vs[v]){
return;
}
vs[v] = true;
if(f){
s += A[v];
}
for(auto i:gr[v]){
spdfs(i,1-f,s);
}
return;
}
int main(){
// int t = 1;
int t;
cin>>t;
while(t--){
for(int i=0;i<8;i++){
cin>>A[i];
gr[i].clear();
}
int p;
cin>>p;
for(int i=0;i<p;i++){
int a,b;
cin>>a>>b;
if(a == b){
continue;
}
a--;
b--;
gr[a].pb(b);
gr[b].pb(a);
}
memset(vs, false , sizeof vs);
vector<vector<int>>cmp;
for(int i=0;i<8;i++){
if(vs[i]){
continue;
}else{
vector<int>tmp;
dfs(i,tmp);
cmp.pb(tmp);
}
}
ll ttl = 0;
for(int i=0;i<cmp.size();i++){
int toadd = INT_MIN;
for(int j=0;j<cmp[i].size();j++){
memset(vs, false,sizeof vs);
int tmp = 0;
spdfs(cmp[i][j], 1, tmp);
toadd = max(toadd,tmp);
}
ttl += toadd;
}
cout<<ttl<<endl;
}
return 0;
}