Defend Your Country

題意：

n個(gè)點(diǎn)，m條邊的簡(jiǎn)單無(wú)向連通圖，每個(gè)點(diǎn)一個(gè)權(quán)值ai,一個(gè)連通塊的貢獻(xiàn)：$(?1{)}^{塊內(nèi)點(diǎn)數(shù)}?\sum a_i[點(diǎn)i在該連通塊內(nèi)]$
可以任意刪除一些邊，求連通塊貢獻(xiàn)之和最大是多少

題解：

如果n是偶數(shù)，此時(shí)貢獻(xiàn)就是所有點(diǎn)的和，顯然不需要?jiǎng)h除任何邊，因?yàn)檫@已經(jīng)是最大貢獻(xiàn)sum
如果是奇數(shù)，我們就需要讓一個(gè)點(diǎn)x脫離其他n-1個(gè)點(diǎn)，此時(shí)答案就是sum-a[x]-a[x]（減的第一個(gè)x是因?yàn)閤點(diǎn)已經(jīng)不在原來(lái)連通塊內(nèi)，再減x是因?yàn)樗菃为?dú)一個(gè)點(diǎn)，按照題目說(shuō)的連通塊貢獻(xiàn)應(yīng)該是-1 * x），所以我們要讓這個(gè)a[x]是最小值
但是這樣就完事了嗎?
并沒(méi)有，因?yàn)槿绻鸻[x]是割點(diǎn)，刪完后還有可能產(chǎn)生額外的連通塊。如果剩下的連通塊中全都是偶數(shù)個(gè)點(diǎn)，此時(shí)x可以刪除。如果其他連通塊中存在一個(gè)是奇數(shù)，那按照貢獻(xiàn)，這個(gè)連通塊是要?jiǎng)h除的，那肯定要比刪除非割點(diǎn)的最小ai更差
總結(jié)：
不是割點(diǎn)，或者是 割點(diǎn)且其他連通塊都是偶數(shù)個(gè) 的點(diǎn)是可以刪除的，然后取最小值，用sum減去起2倍就可以
如何判斷其他連通塊是偶數(shù)
直接在tarjan中寫(xiě)，如圖ok[i]表示該割點(diǎn)去掉之后，是否所有連通塊都是偶數(shù)個(gè)點(diǎn)

我寫(xiě)了情況數(shù)組的init()函數(shù)，然后忘調(diào)用了，調(diào)了我兩小時(shí)。。。。吐了

代碼：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); using namespace std; typedef long long ll; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll=1e18; const int INF_int=0x3f3f3f3f; inline ll read(){ll s=0,w=1ll;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1ll;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10ll+((ch-'0')*1ll),ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } void rd_test(){#ifdef ONLINE_JUDGE#elsestartTime = clock(); //計(jì)時(shí)開(kāi)始freopen("in.txt","r",stdin);#endif } void Time_test(){#ifdef ONLINE_JUDGE#elseendTime = clock(); //計(jì)時(shí)結(jié)束printf("\n運(yùn)行時(shí)間為:%lfs\n",(double)(endTime - startTime) / CLOCKS_PER_SEC);#endif } const int maxn=3e6+9; vector<int>vec[maxn]; int dfn[maxn],low[maxn],deep; int siz[maxn],ok[maxn],cut[maxn]; // u:當(dāng)前點(diǎn) r：本次搜索樹(shù)的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]%2==1)&&low[v]>=dfn[u])ok[u]=0;if (low[v] >= dfn[u] && u != r)cut[u] = 1;//不是根而且他的孩子無(wú)法跨越他回到祖先if (r == u)child++; //如果是搜索樹(shù)的根，統(tǒng)計(jì)孩子數(shù)目}low[u] = min(low[u], dfn[v]);//已經(jīng)搜索過(guò)了}if (child >= 2 && u == r)//如果根節(jié)點(diǎn)的子樹(shù)數(shù)量大于等于2 ,將根節(jié)點(diǎn)去掉之后兩顆子樹(shù)就分離了cut[r] = 1; } ll a[maxn]; int n,m; void init(int n){for(int i=1;i<=n;i++){vec[i].clear();ok[i]=1;low[i]=0;dfn[i]=0;siz[i]=0;cut[i]=0;} } void solve(){cin>>n>>m;ll sum=0;init(n);for(int i=1;i<=n;i++)a[i]=read(),sum+=a[i];for(int i=1;i<=m;i++){int x=read(),y=read();vec[x].push_back(y);vec[y].push_back(x);}if(n%2==0){printf("%lld\n",sum);return ;}for(int i=1;i<=n;i++){if(!dfn[i])tarjan(i,i);}/*刪除非個(gè)點(diǎn)的最小ai */ll minn=1e10;for(int i=1;i<=n;i++){if(!cut[i])//如果不是割點(diǎn) minn=min(minn,a[i]);if(cut[i]&&ok[i])//是割點(diǎn)，且刪除后其他連通分量為偶數(shù) minn=min(minn,a[i]);}printf("%lld\n",sum-2*minn); } int main() {rd_test();int t=read();while(t--){solve();}Time_test(); } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的Defend Your Country的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。