Travelling Businessmen Problem
2024-10-08 16:01:24
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\n",(*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;
}
最新文章
- BZOJ 3261: 最大异或和
- bootstrap-标题
- SharedPreferences保存数据
- win7/IE8无法加载QCbin的插件
- python和pywin32实现窗口查找、遍历和点击
- mapreduce 读写lzo文件
- Delphi - GetUserNameEx（学一下导出Windows API，以及Array Char充当缓冲区的用法，下标必须从零开始）
- OCP读书笔记(10) - 使用闪回技术I
- html练习（5）
- switchhost -- 切换host的工具
- PPT vba从Execl 拷贝图表
- KERBEROS PROTOCOL TUTORIAL
- 记一次linux上的ftp搭建过程
- ssh原理图解
- linux系统（CentOS7）虚拟机上安装oracle 11g，解决oracle图形界面卡住无法点击next问题
- Java7/8 中 HashMap 和 ConcurrentHashMap的对比和分析
- Ex 6_18 硬币有限的兑换问题_第七次作业
- SQL开发测试使用基础
- hdu 3068 最长回文【manacher】(模板题)
- Firewalld防火墙：端口转发与流量均衡