题外话
这一次考试由 boshi 大佬负责译题，出数据，评测。
然而 boshi 大佬显然不满足于译题，出数据，评测。
于是他更改数据范围，缩短时间限制，出卡常数据，提前评测。
litble 同学，您的 L 降为 0，F 降为 1，还剩 1 次怼大佬机会。[^HNOI2017 Day2 T1 大佬的题目描述]
考试策略
看完题目发现只会做 T2，于是高高兴兴花了 40 多分钟的时间打好 T2，调试。
接下来就懵逼了。根据 CY 喜欢把 T1 作为最难的题目定律，我去看了 T3，然后灵机一动想到了一个解法，高高兴兴打好 T3。
又看了 T4，首先以为 T4 是一个以状态作为点的最短路，打完发现样例都过不了（QAQ），接下来又以为 T4 是网络流，打完发现样例都过不了（QAQ），接下来想到了一个暴力搜索+最短路解法，因为 n 的数据范围很小，所以应该还能过一些点，就写了，当时估计会爆栈（结果拿了 85 分？boshi 大佬数据水了？）。
T4 打了一个半小时多，心态爆炸。距离下考还有半个小时，T1 果断输出 “0.000” 骗分，然后检查打了的题，发现 T3 我的解法只能做第一问不能做第二问（QAQ），心想自己要爆 0 了，可是时间又不够了，默默膜了一发 boshi 大佬（弱的人膜强的人会涨 RP 的），就咬牙交了知道是错的程序。
以及……boshi 大佬出的这套题的数据范围全部只给最大范围然后 “数据有梯度”，梯度个鬼啊！天知道是太阳山的梯度还是珠穆朗玛峰的梯度！！！！
T1
期望得分：10 实际得分：15
题目描述：poj3621
题目分析：
赋一首押韵的诗：
分数规划
那是个啥
我不会啊
不如爆炸
首先我们令 X={0,1},Y={0,1}。$V_i$表示点权，$W_i$是边权, 那么 $ANS=\frac{\sum X_iV_i}{\sum Y_jW_j}$。把原式变形可得：$ANS\sum Y_j W_j=\sum X_i V_i$。如果 $ANS$小于 $\frac{\sum X_iV_i}{\sum Y_jW_j}$即 $ANS\sum Y_j W_j $小于 $\sum X_i V_i$时，我们需要把 ANS 缩小。变形得 $ANS \sum Y_j W_j – \sum X_i V_i$小于 0 时。
我们知道奶牛走过的路径一定是一个环（不会是多个环联合，可以用数学方法证明多个环得不到最优解），二分答案，把环上每条边变成（ANS 乘边权-起点点权），然后用 spfa 判断是否有负环即可判断二分下一步干什么。
代码：
（在 poj 上要使用 C++而非 G++才能 A 掉，是因为%lf 的问题）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=1005,M=100005;
int h[N],to[M],ne[M],inq[N],num[N];
double v[N],w[M],dis[N];
int n,m,tot;
int spfa(double lim){
int i,x;queue<int>q;
for(i=1;i<=n;++i)dis[i]=num[i]=0,q.push(i),inq[i]=1;
while(!q.empty()){
x=q.front(),q.pop(),inq[x]=0;
for(i=h[x];i!=-1;i=ne[i])
if(dis[x]-v[x]+w[i]*lim<dis[to[i]]){
dis[to[i]]=dis[x]-v[x]+w[i]*lim;
if(!inq[to[i]]){
inq[to[i]]=1,q.push(to[i]);
++num[to[i]];if(num[to[i]]==n)return 1;
}
}
}
return 0;
}
void add(int x,int y,double z)
{to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
int main()
{
int i,x,y;double l=0,r=1e6,mid,z;
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)scanf("%lf",&v[i]),h[i]=-1;
for(i=1;i<=m;++i)scanf("%d%d%lf",&x,&y,&z),add(x,y,z);
while(l+1e-4<r){
mid=(l+r)/2;
if(spfa(mid))l=mid;
else r=mid;
}
printf("%.2lf",l);
return 0;
}
T2
期望得分：100 实际得分：100
题目描述：HDU3768，其中去的超市数量改为小于等于 15，n 小于等于 10000
题目分析：
显然只有超市和家是有用的节点。我们以每一个超市为起点跑一遍 spfa，得到每个超市和家之间的最短距离，然后状态压缩 dp。用 f(i,zt) 表示当前在 i 号节点（当然超市和家重编号了）时，遍历状态为 zt 的最短路。zt 写成二进制后，如果某一位是 1，则该节点去过了。
方程：f(i,zt)=min(f(j,zt-bin[i])),bin 表示 i 在二进制下哪一位是 1.
细节看代码，另外在 HDU 上可过的搜索做法此处会 T 得很惨。
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define LL long long
int read(){
int q=0;char ch=' ';
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
return q;
}
const int N=100005,M=200005,MAXN=(1<<15);
int n,m,num,tot,T;
LL f[16][MAXN],dis[N];int a[17],bin[17],inq[N];
int h[N],to[M],ne[M];LL w[M],ll[17][17];
void add(int x,int y,LL z)
{to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
void spfa(int x){
queue<int>q;int i,kl;
for(i=0;i<n;++i)dis[i]=1e14,inq[i]=0;
dis[a[x]]=0,q.push(a[x]);
while(!q.empty()){
kl=q.front(),q.pop(),inq[kl]=0;
for(i=h[kl];i!=-1;i=ne[i])
if(dis[kl]+w[i]<dis[to[i]]){
dis[to[i]]=dis[kl]+w[i];
if(!inq[to[i]])q.push(to[i]),inq[to[i]]=1;
}
}
for(i=0;i<=num;++i)ll[x][i]=dis[a[i]];
}
void work(){
int i,zt,lim,j;LL ans=1e14;
lim=(1<<num)-1;
for(i=0;i<=num;++i)for(j=0;j<=lim;++j)f[i][j]=1e14;
f[0][0]=0;
for(zt=1;zt<=lim;++zt){
for(i=1;i<=num;++i){
if(!(zt&bin[i]))continue;
for(j=1;j<=num;++j){
if(!(zt&bin[j]))continue;
f[i][zt]=min(f[i][zt],f[j][zt-bin[i]]+ll[j][i]);
}
f[i][zt]=min(f[i][zt],f[0][zt-bin[i]]+ll[0][i]);
}
for(i=1;i<=num;++i)f[0][zt]=min(f[0][zt],f[i][zt]+ll[i][0]);
}
for(i=1;i<=num;++i)ans=min(ans,f[i][lim]+ll[i][0]);
printf("%lld\n",ans);
}
int main()
{
int i,j,x,y;LL z;
T=read();bin[1]=1;
for(i=2;i<=15;++i)bin[i]=bin[i-1]<<1;
while(T--){
n=read(),m=read();
tot=0;for(i=0;i<n;++i)h[i]=-1;
for(i=1;i<=m;++i){
x=read(),y=read(),z=read();
add(x,y,z),add(y,x,z);
}
num=read();
for(i=1;i<=num;++i)a[i]=read();
for(i=0;i<=num;++i)spfa(i);
work();
}
return 0;
}
T3
期望得分：0 实际得分：12
题目描述：HDU2363，n 改为小于等于 1000
题目分析：
二分海拔差，枚举最小高度，spfa 判断解可行性。
听着不是很难，不过可能被卡时？：
1. 把所有海拔都排个序，二分查找，可以进行 spfa 的最小海拔要求是 $h(i) \leq h(1),h(n) \leq h(i)+lim$。因为 1 号和 n 号节点是必然经过的。
2.spfa 发现满足条件的海拔差后，直接记录答案跳出这次二分枚举。最后再根据记录的答案重新枚举最低点，求出最短路。
关于第二点：显然出题人 boshi 大佬并没有注意这一点，他在记录答案挑出二分枚举的同时直接记录的最短路，这种行为是非常不对的，我用 HDU 的 discuss 区的这组数据 Hack 掉了他的代码（我才不说我 Hack 的理由是看别人的代码都跑得比我的快非常不爽呢）：
1
7 9
4
6
1
3
3
6
4
1 2 1
2 5 1
3 4 1
4 7 1
1 5 4
5 6 4
6 7 4
5 3 4
6 4 2
不过或许是因为在纯随机数据中，出现相同海拔差但是最低最高点不同，导致最短路不同的情况非常罕见，所以像 boshi 大佬那样的代码依然可以 AC。可惜 HDU 没有 Hack 功能啊。
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int read(){
int q=0;char ch=' ';
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
return q;
}
const int N=1005,M=10005;
int h[N],to[M],ne[M],w[M],g[N],inq[N],dis[N],t[N];
int T,n,m,tot,ans1,ans2,inf=1e9+5;
void add(int x,int y,int z)
{to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
int spfa(int mi,int mx){
int i,x;queue<int>q;
for(i=1;i<=n;++i)dis[i]=inf,inq[i]=0;
q.push(1),dis[1]=0;
while(!q.empty()){
x=q.front(),q.pop(),inq[x]=0;
for(i=h[x];i!=-1;i=ne[i]){
int v=to[i];
if(g[v]>=mi&&g[v]<=mx&&dis[x]+w[i]<dis[v]){
dis[v]=dis[x]+w[i];
if(!inq[v])inq[v]=1,q.push(v);
}
}
}
if(dis[n]>=inf)return 0;
else return 1;
}
int ok(int lim){
int i,x=g[1],y=g[n];
if(x>y)swap(x,y);
i=lower_bound(t+1,t+1+n,x)-t;
for(;i>=1&&t[i]+lim>=y;--i)
if(spfa(t[i],t[i]+lim)){ans1=lim;return 1;}
return 0;
}
int main()
{
int i,l,r,mid,x,y,z;
T=read();
while(T--){
n=read(),m=read();tot=l=r=0;
for(i=1;i<=n;++i)
h[i]=-1,g[i]=read(),t[i]=g[i],r=max(r,g[i]);
sort(t+1,t+1+n);
for(i=1;i<=m;++i){
x=read(),y=read(),z=read();
add(x,y,z),add(y,x,z);
}
while(l<=r){
mid=(l+r)>>1;
if(ok(mid))r=mid-1;
else l=mid+1;
}
x=g[1],y=g[n];if(x>y)swap(x,y);ans2=inf;
i=lower_bound(t+1,t+1+n,x)-t;
for(;i>=1&&t[i]+ans1>=y;--i)
if(spfa(t[i],t[i]+ans1))ans2=min(ans2,dis[n]);
printf("%d %d\n",ans1,ans2);
}
return 0;
}
## T4
期望得分：20 实际得分：85
题目描述：HDU3311
题目分析：
—斯坦纳树是什么，能吃吗？
—不能。
—那为什么要考（烤）？
好吧好吧，此题其实是一道斯坦纳树模板题…
我也是无话可说。
或者你说就是一个状压 dp 也行。
我们把开凿水井看作有一个水源，引水入城 [^noip2010]。则水源要和所有寺庙连通。
首先我们玩 n+m+1 次 spfa 来求出任意两点之间的距离 dis(i,j)（很暴力，我喜欢）
我们令 f(zt,i) 为树根为 i，寺庙与树根的连通状态为 zt 的最小权值。那么我们有两种转移方法：
1. 更改树根 f(zt,i)=min(f(zt,j)+dis(i,j))
2. 枚举子集 f(zt,i)=min(f(s,i)+f(zt^s,i))（s 是 zt 的子集）
具体是为什么我也不知道…
什么？你问我 85 分咋拿的？暴力搜索+贪心思想啊。（显然贪心思想是错的，但是 boshi 大佬的数据比较水…）
然后，boshi 大佬这题标程跑了 4 秒多（卡常技巧多到令人发指），就给 5 秒时限，把我们卡得嗷嗷嗷的。
不过，我有特殊的卡常技巧 [^“我有特殊的××技巧” 体，实际上我没有]
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
inline int read(){
int q=0;char ch=' ';
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
return q;
}
int n,m,p,tot,inf=1100000000;
const int N=1010,M=13000;
int h[1010],to[M],ne[M],w[M],dis[N][N],inq[N],bin[7];
int f[(1<<5)][N];
inline void add(int x,int y,int z)
{to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
inline void spfa(){
int x,i,s;queue<int>q;
for(s=0;s<=n+m;++s){
for(i=0;i<=n+m;++i)inq[i]=0,dis[s][i]=inf;
dis[s][s]=0,q.push(s);
while(!q.empty()){
x=q.front(),q.pop(),inq[x]=0;
for(i=h[x];i!=-1;i=ne[i])
if(dis[s][x]+w[i]<dis[s][to[i]]){
dis[s][to[i]]=dis[s][x]+w[i];
if(!inq[to[i]])inq[to[i]]=1,q.push(to[i]);
}
}
}
}
inline void dp(){
int i,j,zt,s;
for(i=1;i<bin[n+1];++i)
for(j=0;j<=n+m;++j)f[i][j]=inf;
for(i=0;i<=n;++i)
for(j=0;j<=n+m;++j)f[bin[i]][j]=dis[i][j];
for(zt=1;zt<bin[n+1];++zt){
if(!(zt&(zt-1)))continue;//跳过只有一个村庄的情况（因为已经搞过了）
for(i=0;i<=n+m;++i){
for(s=zt;s>0;s=(s-1)&zt)
if(f[s][i]+f[zt^s][i]<f[zt][i])
f[zt][i]=f[s][i]+f[zt^s][i];
}
for(i=0;i<=n+m;++i)
for(j=0;j<=n+m;++j)
if(f[zt][j]+dis[j][i]<f[zt][i])
f[zt][i]=f[zt][j]+dis[j][i];
}
}
int main()
{
int x,y,z,i;
bin[1]=1;for(i=2;i<=6;++i)bin[i]=bin[i-1]<<1;
while(scanf("%d%d%d",&n,&m,&p)==3){
tot=0;for(i=0;i<=n+m;++i)h[i]=-1;
for(i=1;i<=n+m;++i)z=read(),add(0,i,z),add(i,0,z);
for(i=1;i<=p;++i){
x=read(),y=read(),z=read();
add(x,y,z),add(y,x,z);
}
spfa();dp();printf("%d\n",f[bin[n+1]-1][0]);
}
return 0;
}
0 条评论