首页 > 其他分享 >题解:【AT icpc2015summer day2-G】 Escape

题解:【AT icpc2015summer day2-G】 Escape

时间:2023-07-05 16:02:15浏览次数:45  
标签:return int 题解 void day2 icpc2015summer inline TT define

题目链接

目前 AT 的最优解。

树的话就是根叶链的最大点权和路径,DP 随便搞。考虑扩展到图上,反复删除掉所有度数为 \(1\) 的节点,显然剩下的东西是可以全部取完的,因为它的形态类似于菊花套环,且末端必定为环。将这部分缩起来再跑上面的 DP 就好了。事实上两部分可以同时进行,一个 bfs 就全做完了。

#include<bits/stdc++.h>
#define ld long double
#define ui unsigned int
#define ull unsigned long long
#define int long long
#define eb emplace_back
#define pb pop_back
#define ins insert
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define power(x) ((x)*(x))
#define gcd(x,y) (__gcd((x),(y)))
#define lcm(x,y) ((x)*(y)/gcd((x),(y)))
#define lg(x,y)  (__lg((x),(y)))
using namespace std;

namespace FastIO
{
    template<typename T=int> inline T read()
    {
        T s=0,w=1; char c=getchar();
        while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
        while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
        return s*w;
    }
    template<typename T> inline void read(T &s)
    {
        s=0; int w=1; char c=getchar();
        while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
        while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
        s=s*w;
    }
    template<typename T,typename... Args> inline void read(T &x,Args &...args)
    {
        read(x),read(args...);
    }
    template<typename T> inline void write(T x,char ch)
    {
        if(x<0) x=-x,putchar('-');
        static char stk[25]; int top=0;
        do {stk[top++]=x%10+'0',x/=10;} while(x);
        while(top) putchar(stk[--top]);
        putchar(ch);
        return;
    }
}
using namespace FastIO;

namespace MTool
{   
    #define TA template<typename T,typename... Args>
    #define TT template<typename T>
    static const int Mod=998244353;
    TT inline void Swp(T &a,T &b) {T t=a;a=b;b=t;}
    TT inline void cmax(T &a,T b) {a=a>b?a:b;}
    TT inline void cmin(T &a,T b) {a=a<b?a:b;}
    TT inline void Madd(T &a,T b) {a=a+b>Mod?a+b-Mod:a+b;}
    TT inline void Mdel(T &a,T b) {a=a-b<0?a-b+Mod:a-b;}
    TT inline void Mmul(T &a,T b) {a=a*b%Mod;}
    TT inline void Mmod(T &a) {a=(a%Mod+Mod)%Mod;}
    TT inline T Cadd(T a,T b) {return a+b>=Mod?a+b-Mod:a+b;}
    TT inline T Cdel(T a,T b) {return a-b<0?a-b+Mod:a-b;}
    TT inline T Cmul(T a,T b) {return a*b%Mod;}
    TT inline T Cmod(T a) {return (a%Mod+Mod)%Mod;}
    TA inline void Madd(T &a,T b,Args... args) {Madd(a,Cadd(b,args...));}
    TA inline void Mdel(T &a,T b,Args... args) {Mdel(a,Cadd(b,args...));}
    TA inline void Mmul(T &a,T b,Args... args) {Mmul(a,Cmul(b,args...));}
    TA inline T Cadd(T a,T b,Args... args) {return Cadd(Cadd(a,b),args...);}
    TA inline T Cdel(T a,T b,Args... args) {return Cdel(Cdel(a,b),args...);}
    TA inline T Cmul(T a,T b,Args... args) {return Cmul(Cmul(a,b),args...);}
    TT inline T qpow(T a,T b) {int res=1; while(b) {if(b&1) Mmul(res,a); Mmul(a,a); b>>=1;} return res;}
    TT inline T qmul(T a,T b) {int res=0; while(b) {if(b&1) Madd(res,a); Madd(a,a); b>>=1;} return res;}
    TT inline T spow(T a,T b) {int res=1; while(b) {if(b&1) res=qmul(res,a); a=qmul(a,a); b>>=1;} return res;}
    TT inline void exgcd(T A,T B,T &X,T &Y) {if(!B) return X=1,Y=0,void(); exgcd(B,A%B,Y,X),Y-=X*(A/B);}
    TT inline T Ginv(T x) {T A=0,B=0; exgcd(x,Mod,A,B); return Cmod(A);}
    #undef TT
    #undef TA
}
using namespace MTool;

inline void file()
{
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
    return;
}

bool Mbe;

namespace LgxTpre
{
    static const int MAX=100010;
    static const int inf=2147483647;
    static const int INF=4557430888798830399;
    static const int mod=1e9+7;
    static const int bas=131;
	
	int n,m,x,y,sum,ans;
	int deg[MAX],val[MAX],tag[MAX],f[MAX];
	vector<int> G[MAX];
	
    inline void lmy_forever()
	{
		read(n,m);
		for(int i=1;i<=n;++i) read(val[i]),sum+=val[i];
		for(int i=1;i<=m;++i) read(x,y),++deg[x],++deg[y],G[x].eb(y),G[y].eb(x);
		
		auto bfs=[&]()->void
		{
			queue<int> q;
			for(int i=2;i<=n;++i) if(deg[i]==1) q.emplace(i);
			while(!q.empty())
			{
				int now=q.front(); q.pop();
				tag[now]=1,sum-=val[now],f[now]+=val[now];
				for(auto to:G[now]) 
				{
					cmax(f[to],f[now]);
					if(to!=1&&--deg[to]==1) q.emplace(to);
				}
			}
		};
		bfs();
		
		for(int i=1;i<=n;++i) if(!tag[i]) cmax(ans,f[i]);
		write(ans+sum,'\n');
    }
}

bool Med;

signed main()
{
    //file();
    fprintf(stderr,"%.3lf MB\n",abs(&Med-&Mbe)/1048576.0);
    int Tbe=clock();
    LgxTpre::lmy_forever();
    int Ted=clock();
    cerr<<1e3*(Ted-Tbe)/CLOCKS_PER_SEC<<" ms\n";
    return (0-0);
}

标签:return,int,题解,void,day2,icpc2015summer,inline,TT,define
From: https://www.cnblogs.com/LittleTwoawa/p/17528750.html

相关文章

  • Springboot No bean named 'XXXXX' available 问题解决
    一、问题描述近日在工作中遇见了一个bug,后端程序频频报错Nobeannamed'XXXXX'available。对比同类程序文件,没有发现有任何特殊之处。在网上搜索方法基本上就是扫描包配置、注解问题、路径问题等,皆不能解决我的问题。排查问题是发现出现问题的类命名不符合驼峰规范,按照这个......
  • B0704 模拟赛题解
    原题链接前言挂分最多的一场。考虑到之前都无分可挂,这场算是最近很简单的了。T1不排序(按理说我的做法不需要排,但挂了),100->40。T2二分某个边界时单调性判错,100->30。T3原,但没做过。T4某人用模拟退火骗到60ptsorz。T1棍子签到题。考虑二分答案。显然每次要切的......
  • SPOJ Substrings 题解
    \(\text{SAM}\)入门好题。首先我们需要知道几个关于\(\text{SAM}\)的结论。结论1:题目中的\(f(x)\)单调下降。显然,对于长度为\(x\)的子串,其必存在一个\(x-1\)的后缀,这个后缀的\(\text{endpos}\)集合肯定包含子串的\(\text{endpos}\)集合,所以必有\(f(x-1)\le......
  • 【安全学习之路】Day29
    ......
  • Hydro #4766. 文艺计算姬 题解--zhengjun
    link前置知识:Prufer序列,二分图别的题解都是直接给答案,没有比较易懂的思路。首先,考虑Prufer序列,发现右边点删除一定会加入一个左边点,另一边类似。且生成Prufer序列的最后一定会留下左右边各一个点。所以左边点在Prufer序列中出现的次数即为\(m-1\),右边即为\(n-1\)。......
  • 【Maven】Unknown lifecycle phase “.test.skip=true“.问题解决
    我们在运行跳过单元测试时的命令mvnpackage-Dmaven.test.skip=true时,出现Unknownlifecyclephase".test.skip=true".如下[ERROR]Unknownlifecyclephase".test.skip=true".Youmustspecifyavalidlifecyclephaseoragoalintheformat<plugin-prefix>......
  • PAT乙级【Java题解合集】
    ✨说在前面       这个暑假博主用大概两周不到的闲暇时间把PAT乙级的110道算法题全部肝完了,个人感觉题目的难度大部分在中等偏下,大概有二十道左右的题目还是蛮有意思的,值得细细去钻研,本专栏非常适合新手入门算法,也适合Java算法老手巩固一些基本知识点,由于C站上关于PAT乙级J......
  • 牛客练习赛 112 B~C题题解
    卡B题了,难受B.qsggandSubarrayB-qsggandSubarray_牛客练习赛112(nowcoder.com)题意给定一个长为n的序列,求有多少个子区间的按位与和为0。思路要想按位与之和为0,那么对于区间的所有数,每个二进制位都要有一个0。设f[i]表示二进制位i的最右边一个0出现的位置,枚举序列的每......
  • ABC306E 题解
    题目链接题目大意维护一个数据结构,数列长度为\(n\),\(q\)次操作,每次操作修改一个位置上的值,每次操作后输出数列里前\(k\)小的数的和(\(k\)是给定的)。\(n,k,q\leq5\times10^5\)值域\(1\times10^9\)题目分析开一棵权值线段树,每个节点储存对应区间的数的个数和数的和,......
  • ABC306F 题解
    题目链接题目大意对于\(S_1\capS_2=\emptyset\),定义长度为\(|S_1|+|S_2|\)的序列\(A\),为\(S_1\cupS_2\)排序后的结果。定义二元函数\(f(S_1,S_2)=\sum\limits_{1\leqi\leq|S_1|+|S_2|}i\times[A_i\inS_1]\)。给定\(n\)个大小为\(m\)的正整数集合\(S\)......