北京房山网站建设产品更新培训,坪地网站建设效果,重庆化工建设信息网站,wordpress葬爱导航Defend Your Country
题意#xff1a;
n个点#xff0c;m条边的简单无向连通图#xff0c;每个点一个权值ai,一个连通块的贡献#xff1a;(−1)块内点数∗∑ai[点i在该连通块内](-1)^{块内点数}*\sum a_{i}[点i在该连通块内](−1)块内点数∗∑ai[点i在该连通块内] 可以…Defend Your Country
题意
n个点m条边的简单无向连通图每个点一个权值ai,一个连通块的贡献(−1)块内点数∗∑ai[点i在该连通块内](-1)^{块内点数}*\sum a_{i}[点i在该连通块内](−1)块内点数∗∑ai[点i在该连通块内] 可以任意删除一些边求连通块贡献之和最大是多少
题解
如果n是偶数此时贡献就是所有点的和显然不需要删除任何边因为这已经是最大贡献sum 如果是奇数我们就需要让一个点x脱离其他n-1个点此时答案就是sum-a[x]-a[x]减的第一个x是因为x点已经不在原来连通块内再减x是因为他是单独一个点按照题目说的连通块贡献应该是-1 * x所以我们要让这个a[x]是最小值 但是这样就完事了吗? 并没有因为如果a[x]是割点删完后还有可能产生额外的连通块。如果剩下的连通块中全都是偶数个点此时x可以删除。如果其他连通块中存在一个是奇数那按照贡献这个连通块是要删除的那肯定要比删除非割点的最小ai更差 总结 不是割点或者是 割点且其他连通块都是偶数个 的点是可以删除的然后取最小值用sum减去起2倍就可以 如何判断其他连通块是偶数 直接在tarjan中写如图ok[i]表示该割点去掉之后是否所有连通块都是偶数个点
我写了情况数组的init()函数然后忘调用了调了我两小时。。。。吐了
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
using namespace std;
typedef long long ll;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll1e18;
const int INF_int0x3f3f3f3f;
inline ll read(){ll s0,w1ll;char chgetchar();while(ch0||ch9){if(ch-)w-1ll;chgetchar();}while(ch0ch9) ss*10ll((ch-0)*1ll),chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
void rd_test(){#ifdef ONLINE_JUDGE#elsestartTime clock(); //计时开始freopen(in.txt,r,stdin);#endif
}
void Time_test(){#ifdef ONLINE_JUDGE#elseendTime clock(); //计时结束printf(\n运行时间为:%lfs\n,(double)(endTime - startTime) / CLOCKS_PER_SEC);#endif
}
const int maxn3e69;
vectorintvec[maxn];
int dfn[maxn],low[maxn],deep;
int siz[maxn],ok[maxn],cut[maxn];
// u:当前点 r本次搜索树的root
void tarjan(ll u, ll r) {dfn[u] low[u] deep;siz[u]1;ll child 0;for (unsigned i 0; i vec[u].size(); i) {ll v vec[u][i];if (!dfn[v]) {tarjan(v, r);siz[u]siz[v];low[u] min(low[u], low[v]);if((siz[v]%21)low[v]dfn[u])ok[u]0;if (low[v] dfn[u] u ! r)cut[u] 1;//不是根而且他的孩子无法跨越他回到祖先if (r u)child; //如果是搜索树的根统计孩子数目}low[u] min(low[u], dfn[v]);//已经搜索过了}if (child 2 u r)//如果根节点的子树数量大于等于2 ,将根节点去掉之后两颗子树就分离了cut[r] 1;
}
ll a[maxn];
int n,m;
void init(int n){for(int i1;in;i){vec[i].clear();ok[i]1;low[i]0;dfn[i]0;siz[i]0;cut[i]0;}
}
void solve(){cinnm;ll sum0;init(n);for(int i1;in;i)a[i]read(),suma[i];for(int i1;im;i){int xread(),yread();vec[x].push_back(y);vec[y].push_back(x);}if(n%20){printf(%lld\n,sum);return ;}for(int i1;in;i){if(!dfn[i])tarjan(i,i);}/*删除非个点的最小ai */ll minn1e10;for(int i1;in;i){if(!cut[i])//如果不是割点 minnmin(minn,a[i]);if(cut[i]ok[i])//是割点且删除后其他连通分量为偶数 minnmin(minn,a[i]);}printf(%lld\n,sum-2*minn);
}
int main()
{rd_test();int tread();while(t--){solve();}Time_test();
}
