Travelling Businessmen Problem
先求出图的两个部分,可能只有一个部分
然后用set模拟,得到不同部分差最小的
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+7;
int n,m;
struct cha
{
int u,v,w;
bool operator<(const cha&r)const
{
if(w!=r.w) return w<r.w;
else if(u!=r.u) return v<r.v;
return u<r.u;
}
} tmp;
struct node
{
int u,col,w;
bool operator<(const node&r)const
{
if(w!=r.w) return w>r.w;
else if(col!=r.col) return col<r.col;
return u>r.u;
}
};
set<cha>ans;
set<node>st;
vector<int>G[maxn];
int val[maxn];
int us[maxn],vis[maxn];
void dfs(int u,int w)
{
if(w==1) us[u]=1;
else if(w==-1) vis[u]=1;
for(int v:G[u])
{
if(w==-1&&!us[v])
{
dfs(v,1);
}
else if(w==1&&!vis[v])
{
dfs(v,-1);
}
}
}
void init()
{
st.clear();
ans.clear();
for(int i=1; i<=n; ++i)
{
st.insert(node{i,us[i],val[i]});
}
set<node>::iterator it,itt;
it=st.begin();
itt=it,++itt;
int u,v,w;
while(itt!=st.end())
{
if((*it).col!=(*itt).col)
{
u=(*it).u;
v=(*itt).u;
w=abs((*it).w-(*itt).w);
if(u>v) swap(u,v);
tmp=cha{u,v,w};
ans.insert(tmp);
}
it++;
itt++;
}
}
void del(int i)
{
node p{i,us[i],val[i]};
set<node>::iterator it,itt,a,b;
it=st.find(p);
int u,v,w;
if(it!=st.begin())
{
itt=it;
--itt;
a=itt;
if((*itt).col!=(*it).col)
{
u=(*it).u;
v=(*itt).u;
w=abs((*it).w-(*itt).w);
if(u>v) swap(u,v);
tmp=cha{u,v,w};
ans.erase(tmp);
}
}
itt=st.end();
--itt;
if(it!=itt)
{
itt=it;
++itt;
b=itt;
if((*itt).col!=(*it).col)
{
u=(*it).u;
v=(*itt).u;
w=abs((*it).w-(*itt).w);
if(u>v) swap(u,v);
tmp=cha{u,v,w};
ans.erase(tmp);
}
if(it!=st.begin())
{
if((*a).col!=(*b).col)
{
u=(*a).u;
v=(*b).u;
w=abs((*a).w-(*b).w);
if(u>v) swap(u,v);
tmp=cha{u,v,w};
ans.insert(tmp);
}
}
}
st.erase(it);
}
void ins(int i,int c)
{
val[i]=c;
node p{i,us[i],val[i]};
st.insert(p);
set<node>::iterator it,itt,a,b;
it=st.find(p);
int u,v,w;
if(it!=st.begin())
{
itt=it;
--itt;
a=itt;
if((*itt).col!=(*it).col)
{
u=(*it).u;
v=(*itt).u;
w=abs((*it).w-(*itt).w);
if(u>v) swap(u,v);
tmp=cha{u,v,w};
ans.insert(tmp);
}
}
itt=st.end();
--itt;
if(it!=itt)
{
itt=it;
++itt;
b=itt;
if((*itt).col!=(*it).col)
{
u=(*it).u;
v=(*itt).u;
w=abs((*it).w-(*itt).w);
if(u>v) swap(u,v);
tmp=cha{u,v,w};
ans.insert(tmp);
}
if(it!=st.begin())
{
if((*a).col!=(*b).col)
{
u=(*a).u;
v=(*b).u;
w=abs((*a).w-(*b).w);
if(u>v) swap(u,v);
tmp=cha{u,v,w};
ans.erase(tmp);
}
}
}
}
void solve()
{
int Q;
scanf("%d",&Q);
int op,u,v;
while(Q--)
{
scanf("%d%d%d",&op,&u,&v);
if(op==0)
{
del(u);
ins(u,v);
}
else
{
if(us[u]==us[v])
{
puts("0");
}
else
{
printf("%d
",(*ans.begin()).w);
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1; i<=n; ++i)
{
scanf("%d",&val[i]);
G[i].clear();
us[i]=vis[i]=0;
}
for(int i=1,u,v; i<=m; ++i)
{
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,1);
init();
solve();
}
return 0;
}