==发现他的课件居然全是题
==我居然重新打了一遍这个
int hd[N],hd2[N],tt,tt2;
struct edge{int v,nxt;}e[M<<1],E[M<<1];
void add(int u,int v){e[++tt]=(edge){v,hd[u]},hd[u]=tt;}
void Add(int u,int v){E[++tt2]=(edge){v,hd2[u]},hd2[u]=tt2;}
queue<int>q;
int mx[N],mn[N];bool vis[N];
void spfa(){
memset(vis,0,sizeof(vis));
memset(mn,inf,sizeof(mn));
q.push(1),vis[1]=1;
while(!q.empty()){
int u=q.front();
q.pop(),vis[u]=0;
for(int i=hd[u],v;i;i=e[i].nxt)
if(mn[v=e[i].v]>Min(a[u],mn[u])){
mn[v]=Min(a[u],mn[u]);
if(!vis[v]) q.push(v),vis[v]=1;
}
}
}
void spfa1(){
memset(vis,0,sizeof(vis));
memset(mx,0,sizeof(mx));
q.push(n),vis[n]=1;
while(!q.empty()){
int u=q.front();
q.pop(),vis[u]=0;
for(int i=hd2[u],v;i;i=E[i].nxt)
if(mx[v=E[i].v]<Max(a[u],mx[u])){
mx[u]=Max(a[u],mx[u]);
if(!vis[v]) q.push(v),vis[v]=1;
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
rd(n),rd(m);
for(int i=1;i<=n;++i) rd(a[i]);
for(int i=1,u,v,ty;i<=m;++i){
rd(u),rd(v),rd(ty);
add(u,v),Add(v,u);
if(ty==2) add(v,u),Add(u,v);
}
spfa(),spfa1();
for(int i=1;i<=n;++i) ans=Max(ans,mx[i]-mn[i]);
printf("%d",ans);
return 0;
}每次都贪心尽量把两个怨气值特别大的两个罪犯拆开
最后得到的就是最优解。因为不这样安排最大的怨气值一定会变大。
一个十分经典的小技巧：对于每一个罪犯??，我们把它拆成两个，分别表 示他自己??和他的死敌?? ′（绝对不能在一间监狱里面）。
这样如果??和??不在一间监狱里面，我们就可以推出来??和?? ′在一间监狱 里面，?? ′和??在一间监狱里面，这样就只需要维护在一间监狱的情况了。 ? 如果处理到一条边的时候发现??和?? ′在一间监狱里面，那就直接不合法
也是很经典的拆点
给你一张\(n\)个点\(m\)条边的带权无向图，每次问你两个点??, ??，问你从??走到 ??经过的边权最小的边最大是多少
某憨憨说这个题很好练模板的
存在限制\((u,v)\) 则以\(v\)为根的子树和\(u\)都不可行
一个可行解内：
? 任意一个限制\((a,b)\)中 \(a\)的子树一定不可行
? 那么标记完不可行的点之后剩下都是可行点
国王游戏
每个大臣获得的金币数分别为：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数 使获得奖赏最多的大臣尽可能少
对于国王身后两个点来分析 队列可能为
? \(L\) \(R\) \(L\) \(R\)
\(king\)： \(a_0\) \(b_0\) \(king\): \(a_0\) \(b_0\)
\(P_1\)： \(a_1\) \(b_1\) \(P_2\)： \(a_2\) \(b_2\)
\(P_2\)： \(a_2\) \(b_2\) \(P_1\)： \(a_1\) \(b_1\)
\(ans1=max(\frac{a_0}{b1},\frac{a_0*a_1}{b_2})\) \(ans_2=max(\frac{a_0}{b_2},\frac{a_0*a_2}{b_1})\)
显然可以得到\(\frac{a_0*a_1}{b_2}>\frac{a_0}{b_2}\),\(\frac{a_0*a_2}{b_1}>\frac{a_0}{b_1}\)
若\(ans_1<ans_2\) 则\(\frac{a_0*a_2}{b_1}>\frac{a_0*a_1}{b_2}\) 即\(a_2*b_2>a_1*b_1\)
所以按\(a_i*b_i\)为关键字来排序就好
皇后游戏
易知大臣所得金币数\(c_i\)是递增的
\(ans=max(max(c_{i-1},sum_{i-1}+a_i)+b_i,sum_{i-1}+a_i+a_{i+1})+b_{i+1}\)
······
struct node{int a,b,d;}a[N];
bool cmp(node x,node y){
if(x.d!=y.d) return x.d<y.d;
if(x.d<=0) return x.a<y.a;
return x.b>y.b;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int T;rd(T);
while(T--){
rd(n);
for(int i=1;i<=n;++i){
rd(a[i].a),rd(a[i].b);
if(a[i].a>a[i].b) a[i].d=1;
else if(a[i].a<a[i].b) a[i].d=-1;
else a[i].d=0;
}
sum=nw=0;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;++i)
sum+=a[i].a,nw=max(nw,sum)+a[i].b;
printf("%lld\n",nw);
}
return 0;
}
原文：https://www.cnblogs.com/lxyyyy/p/11790222.html