强连通分量
POJ 3180: The Cow Prom
找出有多少个点数大于等于2的scc即可。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
找出有多少个点数大于等于2的scc即可。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=10000+5;
const int maxm=50000+5;
const int INF=0x3f3f3f3f;
int n,m,tot=1,cnt=0,ans=0,head[maxn],dfn[maxn],low[maxn],st[maxn],inx[maxn],c[maxn],num=0,top=0,chu[maxn],ru[maxn];
vector<int>scc[maxn];
struct node{
int from,to;
}edge[maxm<<1];
void add(int from,int to){
edge[++tot].to=to;
edge[tot].from=head[from];
head[from]=tot;
}
void tarjan(int x){
dfn[x]=low[x]=++num;
st[++top]=x;
inx[x]=1;
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(inx[y]){
low[x]=min(low[x],dfn[y]);
}
}
if(low[x]==dfn[x]){
int y;
cnt++;
do{
y=st[top];
top--;
inx[y]=0;
c[y]=cnt;
scc[cnt].push_back(y);
}while(x!=y);
}
}
int main() {
// ios::sync_with_stdio(false);
//freopen("The Cow Prom.in","r",stdin);
cin>>n>>m; //n>=2
int from,to;
for(int i=1;i<=m;i++){
scanf("%d%d",&from,&to);
add(from,to);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i);
}
for(int i=1;i<=cnt;i++) if(scc[i].size()>=2) ans++;
cout<<ans;
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 1236: Network of Schools
缩点后先特判只有一个scc的情况。
考虑每个scc的出入度，设出度为0的scc有p个，入度为0的scc有q个。
第一问的答案显然是p，第二问的答案是max(p,q)
解释下第二问答案的来历。
显然，每加入一条有向边，最少让一个点的出度/入度非0，最多让两个点的出度/入度非0。
于是，我们先尽量采取第二种决策。即先将min(p,q)对点解决。然后剩下来的max(p,q)-min(p,q)个点采用第一种决策。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
缩点后先特判只有一个scc的情况
考虑每个scc的出入度，设出度为0的scc有p个，入度为0的scc有q个。
第一问的答案显然是p，第二问的答案是max(p,q)
解释下第二问答案的来历。
显然，每加入一条有向边，最少让一个点的出度/入度非0，最多让两个点的出度/入度非0。
于是，我们先尽量采取第二种决策。即先将min(p,q)对点解决。然后剩下来的max(p,q)-min(p,q)个点采用第一种决策。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
int n,tot=1,cnt=0,head[maxn],p=0,q=0,dfn[maxn],low[maxn],st[maxn],inx[maxn],c[maxn],num=0,top=0,chu[maxn],ru[maxn];
vector<int>scc[maxn];
struct node{
int from,to;
}edge[maxn*maxn*2];
void add(int from,int to){
edge[++tot].to=to;
edge[tot].from=head[from];
head[from]=tot;
}
void tarjan(int x){
dfn[x]=low[x]=++num;
st[++top]=x;
inx[x]=1;
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(inx[y]){
low[x]=min(low[x],dfn[y]);
}
}
if(low[x]==dfn[x]){
int y;
cnt++;
do{
y=st[top];
top--;
inx[y]=0;
c[y]=cnt;
scc[cnt].push_back(y);
}while(x!=y);
}
}
int main() {
ios::sync_with_stdio(false);
//freopen("Network of Schools.in","r",stdin);
cin>>n;
int v;
for(int i=1;i<=n;i++){
while(cin>>v&&v){
add(i,v);
}
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i);
}
if(cnt==1){
cout<<"1"<<endl<<"0";
return 0;
}
for(int i=1;i<=n;i++){
for(int j=head[i];j;j=edge[j].from){
int y=edge[j].to;
if(c[i]!=c[y]){
chu[c[i]]++;
ru[c[y]]++;
}
}
}
for(int i=1;i<=cnt;i++){
if(chu[i]==0) q++;
if(ru[i]==0) p++;
}
cout<<p<<endl<<max(p,q);
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
2-SAT
POJ 3678: Katu Puzzle
2-SAT模板题。
注意建边时，如果给出的某个条件已经能够确定其取值，那么就用一种能够导出矛盾的建边方法。
例如，如果from&to=1，意味着from和to必定都只能取1。因此建边时建立
add(from,from+n);
add(to,to+n);
这样一来，当一个为0的时候，就能导出矛盾。
如果给出的某个条件已经不能够确定其取值，那么就用一种能够“假设型”的建边方法。
例如，如果from&to=0，意味着如果from为1，那么to就要为0。这是from的值不能确定，所以就按照如下方式建边。
add(from+n,to);
add(to+n,from);
即from为1时，能够推出to为0，to为1时，同样能推出from为0。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
2-SAT模板题。
注意建边时，如果给出的某个条件已经能够确定其取值，那么就用一种能够导出矛盾的建边方法。
例如，如果from&to=1，意味着from和to必定都只能取1。因此建边时建立
add(from,from+n);
add(to,to+n);
这样一来，当一个为0的时候，就能导出矛盾。
如果给出的某个条件已经不能够确定其取值，那么就用一种能够“假设型”的建边方法。
例如，如果from&to=0，意味着如果from为1，那么to就要为0。这是from的值不能确定，所以就按照如下方式建边。
add(from+n,to);
add(to+n,from);
即from为1时，能够推出to为0，to为1时，同样能推出from为0。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000*2+5;
const int maxm=1000000*4+5;
const int INF=0x3f3f3f3f;
int n,m;
int head[maxn],tot=1;
int dfn[maxn],low[maxn],cnt=0,st[maxn],num=0,inx[maxn],c[maxn],top=0;
vector<int>scc[maxn];
struct node{
int from,to;
}edge[maxm];
void add(int from,int to){
edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to;
}
void tarjan(int x){
dfn[x]=low[x]=++num;
st[++top]=x;
inx[x]=1;
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(inx[y]){
low[x]=min(low[x],dfn[y]);
}
}
if(dfn[x]==low[x]){
int y;
cnt++;
do{
y=st[top];
top--;
inx[y]=0;
c[y]=cnt;
scc[cnt].push_back(y);
}while(x!=y);
}
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Katu Puzzle.in","r",stdin);
scanf("%d%d",&n,&m);
int from,to,op;
char s[10];
for(int i=1;i<=m;i++){
scanf("%d%d%d%s",&from,&to,&op,s);
from++,to++;
if(s[0]=='A'){
if(op==0){
add(from+n,to);
add(to+n,from);
}
if(op==1){ //from&&to=1 表示两个都必须是1，因此如果一个是0，就导出矛盾
//不能按照注释中建图，原因在于这个条件确定了from和to的取值，不能带入到“如果，就”的语境中去。
// add(from+n,to+n);
// add(to+n,from+n);
add(from,from+n);
add(to,to+n);
}
}
if(s[0]=='O'){
if(op==0){ //from||to=0 表示两个都必须是0，因此如果一个不是0，就导出矛盾
// add(from,to);
// add(to,from);
add(from+n,from);
add(to+n,to);
}
if(op==1){
add(from,to+n);
add(to,from+n);
}
}
if(s[0]=='X'){
if(op==0){
add(from,to);
add(to,from);
add(from+n,to+n);
add(to+n,from+n);
}
if(op==1){
add(from+n,to);
add(from,to+n);
add(to,from+n);
add(to+n,from);
}
}
}
for(int i=1;i<=2*n;i++) if(!dfn[i]) tarjan(i);
int flag=1;
for(int i=1;i<=n;i++) if(c[i]==c[i+n]) flag=0;
flag?cout<<"YES":cout<<"NO";
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 2723: Get Luffy Out
读懂题意后，2-SAT正常建图即可。
对于两个有关系的钥匙a和b，建边(a+2n,b)，(b+2n,a)表示如果选了a就不能选b，选了b就不能选a。
同理，对于门锁需要的钥匙a和b，显然满足a||b=0，即如果a为1，b就为0，a为0，b就为1，于是建边(a,b+2n)，(b,a+2n)。
因为有开门顺序，所以二分答案后，每次重新建一次图，然后用tarjan判断是否矛盾即可。
注意一个天坑：题目说的是有n对钥匙，就有2n个钥匙，就有4n个布尔变量。也就是说，a的对应点是a+2*n而不是a+n。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
读懂题意后，2-SAT正常建图即可。
对于两个有关系的钥匙a和b，建边(a+2*n,b)，(b+2*n,a)表示如果选了a就不能选b，选了b就不能选a。
同理，对于门锁需要的钥匙a和b，显然满足a||b=0，即如果a为1，b就为0，a为0，b就为1，于是建边(a,b+2*n)，(b,a+2*n)。
因为有开门顺序，所以二分答案后，每次重新建一次图，然后用tarjan判断是否矛盾即可。
注意一个天坑：题目说的是有n对钥匙，就有2*n个钥匙，就有4*n个布尔变量。也就是说，a的对应点是a+2*n而不是a+n。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1024*4+5; //题目说的是有n对钥匙，就有2*n个钥匙，就有4*n个布尔变量。
const int maxm=1024*4+2048*4+5;
const int INF=0x3f3f3f3f;
int n,m;
int head[maxn],tot=1;
int dfn[maxn],low[maxn],cnt,st[maxn],num,inx[maxn],c[maxn],top;
//vector<int>scc[maxn];
struct node{
int from,to;
}edge[maxm];
inline void init(){
tot=1;memset(head,0,sizeof(head));
// for(int i=1;i<=cnt;i++) scc[i].clear();
cnt=0,num=0,top=0;
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(st,0,sizeof(st));
memset(inx,0,sizeof(inx));
memset(c,0,sizeof(c));
}
inline void add(int from,int to){
edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to;
}
void tarjan(int x){
dfn[x]=low[x]=++num;
st[++top]=x;
inx[x]=1;
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(inx[y]){
low[x]=min(low[x],dfn[y]);
}
}
if(dfn[x]==low[x]){
int y;
cnt++;
do{
y=st[top];
top--;
inx[y]=0;
c[y]=cnt;
// scc[cnt].push_back(y);
}while(x!=y);
}
}
int a[maxm],b[maxm],e1[maxn],e2[maxn];
bool check(int mid){
init();
for(int i=1;i<=n;i++) add(e1[i]+2*n,e2[i]),add(e2[i]+2*n,e1[i]);
for(int i=1;i<=mid;i++){
add(a[i],b[i]+2*n),add(b[i],a[i]+2*n);
}
for(int i=1;i<=4*n;i++) if(!dfn[i]) tarjan(i);
for(int i=1;i<=2*n;i++) if(c[i]==c[i+2*n]) return 0;
return 1;
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Get Luffy Out.in","r",stdin);
while(~scanf("%d%d",&n,&m)){
if(!n&&!m) break;
for(int i=1;i<=n;i++){
// cin>>e1[i]>>e2[i];
scanf("%d%d",&e1[i],&e2[i]);
e1[i]++,e2[i]++;
}
// for(int i=1;i<=m;i++) cin>>a[i]>>b[i],a[i]++,b[i]++;
for(int i=1;i<=m;i++) scanf("%d%d",&a[i],&b[i]),a[i]++,b[i]++;
int l=0,r=m,ans;
while(l<=r){
int mid=l+r>>1;
if(check(mid)) l=mid+1,ans=mid;
else r=mid-1;
}
// cout<<l<<endl;
printf("%d\n",ans);
// int l=0,r=m;
// while(l<r){
// int mid=l+r+1>>1;
// if(check(mid)) l=mid;
// else r=mid-1;
// }
//// cout<<l<<endl;
// printf("%d\n",l);
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 2749: Building roads
二分答案后建图即可。
注意两个点i和j之间的建图过程。
显然，如果i和j只见满足某个距离条件时，很难确定他们的选择。
但如果他们间的距离出现矛盾时，就比较容易建立“只要一个确定，另一个也确定”的条件。
假设目前二分答案为mid，两个中转点之间的距离为len，i到第一个点的距离为d1[i]，i到第二个点的距离为d2[i]。
则按照如下方式建图。
if(d1[i]+d1[j]>mid){ //i和j不能同时选择通过第一个中转点。即如果i和j中的一个选了第一个中转点，另一个就要选择第二个中转点
add(i,j+n); //如果i选择了第一个中转点，j就只能选择第二个中转点
add(j,i+n);
}
if(d2[i]+d2[j]>mid){ //与上同理
add(i+n,j);
add(j+n,i);
}
if(d1[i]+d2[j]+len>mid){ //如果i选择了第一个中转点，j选择了第二个中转点，i和j之间的距离会不满足当前答案。即i和j要选择同一个中转点。
add(i,j);
add(j+n,i+n);
}
if(d2[i]+d1[j]+len>mid){ //与上同理
add(i+n,j+n);
add(j,i);
}
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
二分答案后建图即可。
注意两个点i和j之间的建图过程。
显然，如果i和j只见满足某个距离条件时，很难确定他们的选择。
但如果他们间的距离出现矛盾时，就比较容易建立“只要一个确定，另一个也确定”的条件。
假设目前二分答案为mid，两个中转点之间的距离为len，i到第一个点的距离为d1[i]，i到第二个点的距离为d2[i]。
则按照如下方式建图。
if(d1[i]+d1[j]>mid){ //i和j不能同时选择通过第一个中转点。即如果i和j中的一个选了第一个中转点，另一个就要选择第二个中转点
add(i,j+n); //如果i选择了第一个中转点，j就只能选择第二个中转点
add(j,i+n);
}
if(d2[i]+d2[j]>mid){ //与上同理
add(i+n,j);
add(j+n,i);
}
if(d1[i]+d2[j]+len>mid){ //如果i选择了第一个中转点，j选择了第二个中转点，i和j之间的距离会不满足当前答案。即i和j要选择同一个中转点。
add(i,j);
add(j+n,i+n);
}
if(d2[i]+d1[j]+len>mid){ //与上同理
add(i+n,j+n);
add(j,i);
}
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=2000+5;
const int maxm=5000005+5;
const int INF=0x3f3f3f3f;
int n,A,B,x[maxn],y[maxn],h1[maxn],h2[maxn],f1[maxn],f2[maxn];
int len;//两个中间点之间的距离
int d1[maxn],d2[maxn];
int head[maxn],tot;
int dfn[maxn],low[maxn],cnt,st[maxn],num,inx[maxn],c[maxn],top;
struct node {
int from,to;
} edge[maxm];
void add(int from,int to) {
edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to;
}
void tarjan(int x) {
dfn[x]=low[x]=++num;
st[++top]=x;
inx[x]=1;
for(int i=head[x]; i; i=edge[i].from) {
int y=edge[i].to;
if(!dfn[y]) {
tarjan(y);
low[x]=min(low[x],low[y]);
} else if(inx[y]) {
low[x]=min(low[x],dfn[y]);
}
}
if(dfn[x]==low[x]) {
int y;
cnt++;
do {
y=st[top];
top--;
inx[y]=0;
c[y]=cnt;
} while(x!=y);
}
}
int dis(int i,int j) {
return abs(x[i]-x[j])+abs(y[i]-y[j]);
}
inline void init() {
tot=1;
memset(head,0,sizeof(head));
cnt=0,num=0,top=0;
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(st,0,sizeof(st));
memset(inx,0,sizeof(inx));
memset(c,0,sizeof(c));
}
bool check(int mid) {
init();
for(int i=1; i<=A; i++) add(h1[i],h2[i]+n),add(h2[i],h1[i]+n),add(h2[i]+n,h1[i]),add(h1[i]+n,h2[i]);
for(int i=1; i<=B; i++) add(f1[i],f2[i]),add(f2[i],f1[i]),add(f2[i]+n,f1[i]+n),add(f1[i]+n,f2[i]+n);
for(int i=1; i<=n; i++) {
for(int j=i+1; j<=n; j++) {
// if(i==j) continue;
if(d1[i]+d1[j]>mid) {
add(i,j+n);
add(j,i+n);
}
if(d2[i]+d2[j]>mid) {
add(i+n,j);
add(j+n,i);
}
if(d1[i]+d2[j]+len>mid) {
add(i,j);
add(j+n,i+n);
}
if(d2[i]+d1[j]+len>mid) {
add(i+n,j+n);
add(j,i);
}
}
}
for(int i=1; i<=2*n; i++) if(!dfn[i]) tarjan(i);
for(int i=1; i<=n; i++) if(c[i]==c[i+n]) return false;
return true;
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Building roads.in","r",stdin);
scanf("%d%d%d",&n,&A,&B); //1~n n+1~2n
scanf("%d%d%d%d",&x[2*n+1],&y[2*n+1],&x[2*n+2],&y[2*n+2]); //2n+1 2n+2
len=dis(2*n+1,2*n+2);
// D(len);E;
for(int i=1; i<=n; i++) {
scanf("%d%d",&x[i],&y[i]);
d1[i]=dis(i,2*n+1),d2[i]=dis(i,2*n+2);
// D(d1[i]);D(d2[i]);E;
}
for(int i=1; i<=A; i++) scanf("%d%d",&h1[i],&h2[i]);
for(int i=1; i<=B; i++) scanf("%d%d",&f1[i],&f2[i]);
int l=0,r=INF;
while(l<r) {
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
if(l==INF) printf("-1");
else printf("%d",l);
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
LCA
POJ 1986: Distance Queries
模板题，不赘述。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=3e6+5;
const int INF=0x3f3f3f3f;
int n,m;
struct node {
int from,to,w;
} edge[maxn];
int t,head[maxn],tot=0,ans[maxn],fa[maxn][20],d[maxn],dis[maxn];
void add(int u,int v,int w) {
edge[++tot].to=v;
edge[tot].from=head[u];
edge[tot].w=w;
head[u]=tot;
}
void bfs() {
queue<int>q;
q.push(1);
d[1]=1;
while(!q.empty()) {
int x=q.front();
q.pop();
for(int i=head[x]; i!=-1; i=edge[i].from) {
int y=edge[i].to,w=edge[i].w;
if(!d[y]) {
q.push(y);
d[y]=d[x]+1;
dis[y]=dis[x]+w;
fa[y][0]=x;
for(int j=1; j<=t; j++) {
fa[y][j]=fa[fa[y][j-1]][j-1];
}
}
}
}
}
int lca(int x,int y) {
if(d[x]>d[y]) swap(x,y);
for(int i=t; i>=0; i--) {
if(d[fa[y][i]]>=d[x]) {
y=fa[y][i];
}
}
if(x==y) return x;
for(int i=t; i>=0; i--) {
if(fa[x][i]!=fa[y][i]) {
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Distance Queries.in","r",stdin);
memset(head,-1,sizeof(head));
cin>>n>>m;
// t=(int)(log(n)/log(2))+1; //这两种写法写在poj会报如下错误
// t=(int)(log(double(n))/log(2))+1; //这两种写法写在poj会报如下错误
/*
F:\temp\20869669.63353\Main.cpp(81) : error C2668: 'log' : ambiguous call to overloaded function
math.h(567): could be 'long double log(long double)'
math.h(519): or 'float log(float)'
math.h(121): or 'double log(double)'
while trying to match the argument list '(int)'
*/
t=int((log(double(n))/log(2.0)))+1;
int u,v,w;
// char s[10];
string s;
for(int i=1; i<=m; i++) {
scanf("%d%d%d",&u,&v,&w);
scanf("%s",&s[0]);//这里不能写成 scanf("%s",s);
add(u,v,w);
add(v,u,w);
}
bfs();
int q;
cin>>q;
while(q--){
scanf("%d%d",&u,&v);
printf("%d\n",dis[u]+dis[v]-2*dis[lca(u,v)]);
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 3728: The merchant
因为存在买卖顺序的问题，问题不能单纯的理解为在树链上求解最值。
考虑答案的产生过程，有三种情况。
1 在from到lca的过程中完成买卖。
2 在lca到to的过程中完成买卖。
3 在from到lca的过程中以这一段的最低价格买入，在lca到to的过程中以这一段的最高价格卖出。
因此将深度进行二进制划分，完成几个数组的dp。
up数组，up[i][j]维护i到i节点往上2^j的节点的最大差价
down数组，down[i][j]维护i节点往下2^j到i的节点的最大差价
Max数组, Max[i][j]维护i到i节点往上2^j的节点之间价格的最大值
Min数组，Min[i][j]维护i到i节点往上2^j的节点之间价格的最小值
最后答案通过组合这些二进制数组得到。具体内容详见注释。本题在转移时细节较多，需要细心。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
因为存在买卖顺序的问题，问题不能单纯的理解为在树链上求解最值。
考虑答案的产生过程，有三种情况。
1 在from到lca的过程中完成买卖。
2 在lca到to的过程中完成买卖。
3 在from到lca的过程中以这一段的最低价格买入，在lca到to的过程中以这一段的最高价格卖出。
因此将深度进行二进制划分，完成几个数组的dp。
up数组，up[i][j]维护i到i节点往上2^j的节点的最大差价
down数组，down[i][j]维护i节点往下2^j到i的节点的最大差价
Max数组, Max[i][j]维护i到i节点往上2^j的节点之间价格的最大值
Min数组，Min[i][j]维护i到i节点往上2^j的节点之间价格的最小值
最后答案通过组合这些二进制数组得到。具体内容详见注释。本题在转移时细节较多，需要细心。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=50000+5;
const int INF=0x3f3f3f3f;
int n,q;
struct node {
int from,to;
} edge[maxn<<1];
int t,head[maxn],tot=0,fa[maxn][20],d[maxn],w[maxn],up[maxn][20],down[maxn][20],Max[maxn][20],Min[maxn][20];
/*
up数组，up[i][j]维护i到i节点往上2^j的节点的最大差价
down数组，down[i][j]维护i节点往下2^j到i的节点的最大差价
Max数组, Max[i][j]维护i到i节点往上2^j的节点之间价格的最大值
Min数组，Min[i][j]维护i到i节点往上2^j的节点之间价格的最小值
*/
void add(int u,int v) {
edge[++tot].to=v;edge[tot].from=head[u];head[u]=tot;
}
void bfs() {
queue<int>q;
q.push(1);
d[1]=1;
while(!q.empty()) {
int x=q.front();
q.pop();
for(int i=head[x]; i; i=edge[i].from) {
int y=edge[i].to;
if(!d[y]) {
q.push(y);
d[y]=d[x]+1;
Max[y][0]=max(w[x],w[y]);
Min[y][0]=min(w[x],w[y]);
up[y][0]=max(0,w[x]-w[y]);
// D(x);D(y);D(w[x]);D(w[y]);D(up[y][0]);E;
down[y][0]=max(0,w[y]-w[x]);
fa[y][0]=x;
int res1,res2;
for(int j=1; j<=t; j++) {
fa[y][j]=fa[fa[y][j-1]][j-1];
Max[y][j]=max(Max[y][j-1],Max[fa[y][j-1]][j-1]);
Min[y][j]=min(Min[y][j-1],Min[fa[y][j-1]][j-1]);
res1=max(0,Max[fa[y][j-1]][j-1]-Min[y][j-1]);
res2=max(up[fa[y][j-1]][j-1],up[y][j-1]);
// D(y);D(j);D(res1);D(res2);D(Max[fa[y][j-1]][j-1]);D(Min[y][j-1]);E;
up[y][j]=max(res1,res2);
res1=max(0,Max[y][j-1]-Min[fa[y][j-1]][j-1]);
res2=max(down[fa[y][j-1]][j-1],down[y][j-1]);
down[y][j]=max(res1,res2);
}
}
}
}
}
int lca(int x,int y) {
if(d[x]>d[y]) swap(x,y);
for(int i=t; i>=0; i--) {
if(d[fa[y][i]]>=d[x]) {
y=fa[y][i];
}
}
if(x==y) return x;
for(int i=t; i>=0; i--) {
if(fa[x][i]!=fa[y][i]) {
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
int query_up(int x,int dep,int &val){ //val:x到lca的最大差值
val=0;
int res=INF; //res:x到lca的最小值
for(int i=t;i>=0;i--){
if(dep&(1<<i)){
val=max(val,up[x][i]);
val=max(val,Max[x][i]-res); //先算val保证此时的res表示的最小值一定在x以下（即对应点深度大于x）
res=min(res,Min[x][i]);
x=fa[x][i];
}
}
return res;
}
int query_down(int x,int dep,int &val){ //val:lca到x的最大差值
val=0;
int res=0; //res:lca到x的最大值
for(int i=t;i>=0;i--){
if(dep&(1<<i)){
val=max(val,down[x][i]);
val=max(val,res-Min[x][i]); //先算val保证此时的res表示的最小值一定在x以上（即对应点深度小于x）
res=max(res,Max[x][i]);
x=fa[x][i];
}
}
return res;
}
int main() {
// ios::sync_with_stdio(false);
//freopen("The merchant.in","r",stdin);
scanf("%d",&n);
t=int((log(double(n))/log(2.0)))+1;
// D(t);E;
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
int from,to;
for(int i=1;i<=n-1;i++) scanf("%d%d",&from,&to),add(from,to),add(to,from);
bfs();
/*
for(int i=1;i<=n;i++){
for(int j=0;j<=t;j++){
D(i);D(j);D(Min[i][j]);D(Max[i][j]);D(up[i][j]);D(down[i][j]);E;
}
E;
}
*/
scanf("%d",&q);
while(q--){
scanf("%d%d",&from,&to);
int temp=lca(from,to);
int a,b,val1,val2;
//a:from到lca的最小值
//b:lca到to的最大值
//val1:from到lca的最大差价
//val2:lca到to的最大差价
a=query_up(from,d[from]-d[temp],val1);
b=query_down(to,d[to]-d[temp],val2);
int ans=max(0,max(max(val1,val2),b-a));
printf("%d\n",ans);
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
网友评论