题目传送门
话说这道题不分析样例实在是太亏了... 结论题啊...
但是话说回来不知道它是结论题的时候会不会想到猜结论呢... 毕竟样例一, 二都有些特殊.
观察样例发现选中的子图都只有一条边.
于是猜只有一条边的时候解最优.
飞快地写个暴力, 然后和结论对拍, 然后假装这个结论是对的, 然后就 $AC$ 了 (大雾
还是证明一下这个结论吧:
用反证法.
设这样三个点的点权分别为 $A$,$B$,$C$, 两条边的边权为 $n$,$m$
假设子图中有 $A,B,C$ 三个点比只有两个点更优.
也就是三个点都选的答案比只选 $AB$ 和只选 $BC$ 都大.
三个都选的答案:$(A+B+C)/(n+m)$
只选 $AB$:$(A+B)/m$
只选 $BC$:$(B+C)/n$
则:
- $$(A+B+C)/(n+m)>(A+B)/m$$
- $$(A+B+C)/(n+m)>(B+C)/n$$
化简:(权都是正数)
- $$(A+B+C)*m>(A+B)*(n+m)$$
- $$(A+B+C)*n>(B+C)*(n+m)$$
$$↓$$
- $$C*m>A*n+B*n$$
- $$A*n>B*m+C*m$$
相加:
- $$C*m+A*n>A*n+B*n+B*m+C*m$$
- $0>B*n+B*m$
由于 $B$ 和 $n$,$m$ 都是正数, 导出矛盾.
所以假设不成立.
另外, 如果 $AC$ 之间有连边的话, 那三个都选肯定更不优, 分子不变, 分母变大了嘛. 只选 $AC$ 都不用讨论, 至少在这种情况下三个都选干不过只选 $AB$ 或 $BC$.
暴力程序 (拿来对拍)
有同学写的 $2^n$ 枚举子集的暴力, 我觉得略麻烦, 还是更喜欢自己的 (笑)
甚至还想优化一下自己的暴力, 就是在以 $1$ 以外的点为起点的时候, 就不把 $1$ 加进去, 因为 $1$ 有的状态已经在 $1$ 为起点的算过了.
但是反正是拿来写对拍嘛, 节约考试时间.
- #include<cstdio>
- #include<algorithm>
- #include<vector>
- #include<queue>
- using namespace std;
- #define N 505
- #define ll long long
- int n,m;
- int a[N];
- bool vis[N];
- double ans=0.0;
- vector<pair<int,int>>G[N];
- int rd()
- {
- int f=1,x=0;char c=getchar();
- while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
- while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
- return f*x;
- }
- void dfs(int u,int d,int b)
- {
- for(int i=0;i<G[u].size();i++)
- {
- int v=G[u][i].first;
- if(vis[v]) continue;
- vis[v]=1;
- int tmp=0;
- for(int j=0;j<G[v].size();j++)
- if(vis[G[v][j].first]) tmp+=G[v][j].second;
- dfs(v,d+a[v],b+tmp);
- vis[v]=0;
- }
- if(b==0) return ;
- ans=max(ans,1.0*d/b);
- }
- int main()
- {
- n=rd(),m=rd();
- for(int i=1;i<=n;i++)
- a[i]=rd();
- for(int i=1;i<=m;i++)
- {
- int u=rd(),v=rd(),w=rd();
- G[u].push_back(make_pair(v,w));
- G[v].push_back(make_pair(u,w));
- }
- for(int i=1;i<=n;i++)
- {
- vis[i]=1;
- dfs(i,a[i],0);
- vis[i]=0;
- }
- printf("%.9f\n",ans);
- return 0;
- }
- // 不分析样例真的是个不好的习惯啊
- Code
正解程序:(比暴力好写)
- #include<cstdio>
- #include<algorithm>
- #include<vector>
- #include<queue>
- using namespace std;
- #define N 505
- #define ll long long
- int n,m;
- int a[N];
- double ans=0.0;
- int rd()
- {
- int f=1,x=0;char c=getchar();
- while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
- while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
- return f*x;
- }
- int main()
- {
- n=rd(),m=rd();
- for(int i=1;i<=n;i++)
- a[i]=rd();
- for(int i=1;i<=m;i++)
- {
- int u=rd(),v=rd(),w=rd();
- ans=max(ans,1.0*(a[u]+a[v])/w);
- }
- printf("%.9f\n",ans);
- return 0;
- }
- Code
来源: http://www.bubuko.com/infodetail-3287982.html