ZOJ 3649배 증법 DP, 트리 체인 분할, tarjan 및 쿼리
Submit
Status
Practice
ZOJ 3649
Description
There are n individuals(2 <= n <= 30000). Everyone has one or more friends. And everyone can contact all people by friend-relation. If two persons aren't friends, they also can contact by their friends. Each pair of friends have a friendship value ai(1 <= ai <= 50000).
Firstly, you will relieve some friend-relation. The rest of the friend-relation is the social net. The net is unique in all test cases. In this net, everyone can contact all people by rest friend-relation. The net has a minimum number of friend-relation. And the net has maximum sum of friendship value. We want to get the maximum sum.
Secondly, everyone has an angry value bi(1 <= bi <= 100000). We have q operations(1 <= q <= 30000): Person X wants to contact person Y, this operation merely has one sequence which describes the process. The sequence consists of persons' angry value. The persons are on the process.
We suppose the sequence is c1, c2, c3, ... ,ci. Here ci means the angry value of the ith people in the sequence.
We attempt to find the maximum ck-cj (ck >= cj, j <= k).
Example:
The sequence is 3(X), 4, 5, 6, 7, 5, 9, 4, 11(Y). The maximum ck-cj is 11-3=8.
The sequence is 3(X), 4, 5, 6, 7, 5, 9, 2, 11(Y). The maximum ck-cj is 11-2=9.
The sequence is 3(X), 10, 2, 5(Y). The maximum ck-cj is 10-3=7.
Input
The input contains multiple test cases. Each test case begins with a line containing a single integer n. The following line contains nintegers bi.
The subsequent line describe the number of relations m(n <= m <= 50000). The next m lines contain the information about relations: x, y,ai. Their friendship value is ai.
Afterward gives q. The next q lines contain the operations: x, y. person X wants to contact person Y.
Output
For each case, print maximum sum of friendship value of the net on the first line.
The next q lines contain the answers of every operations.
Sample Input
6
3 5 1 7 3 5
7
1 2 5
1 3 6
2 4 7
2 5 8
3 6 9
4 5 1
5 6 2
5
6 1
6 2
6 3
6 4
6 5
Sample Output
35
2
4
0
6
4
어쨌든
최대 스패닝 트리
U-to-LCA의 최대치, 최소치, U-to-LCA의 최우수치, LCA-to-U의 최우수치 등 4개 도메인 유지 관리
Tarjan 오프라인 처리
수집을 처리하고 조사할 때 네 개의 영역을 유지하려면 반드시 위의 점을 유지하고 아래의 점을 유지해야 한다
질의의 종점이 이미 액세스한 지점인 경우 LCA에 직접 연결
그리고 다 훑어보고 나서 LCA를 점검하고 모으도록 하겠습니다.
// whn6325689
// Mr.Phoebe
// http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;
#define CLR(x,y) memset(x,y,sizeof(x))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))
#define MID(x,y) (x+((y-x)>>1))
#define speed std::ios::sync_with_stdio(false);
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1;
char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
template <class T>
inline void write(T n)
{
if(n < 0)
{
putchar('-');
n = -n;
}
int len = 0,data[20];
while(n)
{
data[len++] = n%10;
n /= 10;
}
if(!len) data[len++] = 0;
while(len--) putchar(data[len]+48);
}
//-----------------------------------
const int MAXN=50010;
struct edge
{
int u,v,w;
bool operator < (const edge & b) const{return w>b.w;}
}ee[MAXN<<1];
struct Edge
{
int to,next;
}e[MAXN<<1],lca[MAXN<<1];
struct query
{
int u,v,next;
int id;
}q[MAXN<<1];
int h[MAXN],qh[MAXN],lh[MAXN];
int vis[MAXN],ma[MAXN],mi[MAXN],up[MAXN],down[MAXN];
int n,m,qq,tot,cnt,num,ans[MAXN],angry[MAXN];
void update(int u,int v);
struct disjoint
{
int fa[MAXN];
void init(int n)
{
for(int i=0;i<=n;i++)
fa[i]=i;
}
int find_fa(int u)
{
return (u == fa[u]) ? fa[u] : (fa[u] = find_fa(fa[u]));
}
int find(int u)
{
if(u==fa[u]) return fa[u];
int v=fa[u];
fa[u]=find(fa[u]);
update(u,v);
return fa[u];
}
void merge(int u,int v)
{
fa[u]=v;
}
}st;
void init(int n)
{
CLR(h,-1);CLR(qh,-1);CLR(lh,-1);CLR(vis,0);
tot=cnt=num=0;
st.init(n);
}
void update(int u,int v) //
{
//cout<<"fa:"<<u<<" "<<v<<endl;
up[u]=max(ma[v]-mi[u],max(up[u],up[v]));
down[u]=max(ma[u]-mi[v],max(down[u],down[v]));
ma[u]=max(ma[u],ma[v]);
mi[u]=min(mi[u],mi[v]);
}
void addedge(int u,int v)
{
e[tot].to=v;
e[tot].next=h[u];
h[u]=tot++;
}
void addquery(int u,int v,int w)
{
q[cnt].u=u;
q[cnt].v=v;
q[cnt].id=w;
q[cnt].next=qh[u];
qh[u]=cnt++;
}
void Kruskal()
{
sort(ee,ee+m);
int sum=0;
for(int i=0;i<m;i++)
{
int u=st.find_fa(ee[i].u);
int v=st.find_fa(ee[i].v);
if(u!=v)
{
st.merge(v,u);
sum+=ee[i].w;
addedge(ee[i].u,ee[i].v);addedge(ee[i].v,ee[i].u);
//cout<<ee[i].u<<" "<<ee[i].v<<endl;
}
}
write(sum),putchar('
');
}
void dfs(int u)
{
vis[u]=1;
for(int i=qh[u];~i;i=q[i].next) // LCA
{
if(vis[q[i].v])
{
int xx=st.find(q[i].v);
lca[num].to=i; // ，
lca[num].next=lh[xx];
lh[xx]=num++;
}
}
for(int i=h[u];~i;i=e[i].next)
{
if(vis[e[i].to]) continue;
dfs(e[i].to);
st.merge(e[i].to,u); // father
}
for(int i=lh[u];~i;i=lca[i].next)
{
int j=lca[i].to;
int u=q[j].u,v=q[j].v;
st.find(u);//st.find(v);
if(j&1) // ，
swap(u,v);
ans[q[j].id]=max(ma[v]-mi[u],max(up[u],down[v]));// u->v
//cout<<q[j].id<<" "<<ans[q[j].id]<<endl;
}
}
int main()
{
//freopen("data.txt","r",stdin);
//freopen("w.txt","w",stdout);
while(read(n))
{
init(n);
for(int i=1;i<=n;i++)
{
read(angry[i]);
ma[i]=mi[i]=angry[i];
up[i]=down[i]=0;
}
read(m);
for(int i=0;i<m;i++)
read(ee[i].u),read(ee[i].v),read(ee[i].w);
read(qq);
for(int i=0,u,v;i<qq;i++)
{
read(u),read(v);
addquery(u,v,i);addquery(v,u,i);
}
Kruskal();
st.init(n);
dfs(1);
for(int i=0;i<qq;i++)
write(ans[i]),putchar('
');
}
return 0;
}LCA를 배로 늘리는 방법으로 온라인으로 구하다
#include <bits/stdc++.h>
struct node {
int from, to, cost;
bool operator < (const node &rhs) const {
return cost > rhs.cost;
}
};
node edge[50010];
int fa[50010];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int to[50010<<1], pre[50010<<1], tail[50010];
int e_tot = 0;
inline void add(int _from, int _to) {
to[e_tot] = _to;
pre[e_tot] = tail[_from];
tail[_from] = e_tot++;
}
void getEdge(int n) {
for(int i = 1; i <= n; ++i)
fa[i] = i;
int m;
scanf("%d", &m);
for(int i = 0; i < m; ++i)
scanf("%d%d%d", &edge[i].from, &edge[i].to, &edge[i].cost);
std::sort(edge, edge + m);
long long ans = 0;
e_tot = 0;
memset(tail, -1, sizeof tail);
for(int i = 0; i < m; ++i) {
int pu = find(edge[i].from), pv = find(edge[i].to);
if(pu != pv) {
add(edge[i].from, edge[i].to);
add(edge[i].to, edge[i].from);
ans += edge[i].cost;
fa[pu] = pv;
}
}
printf("%lld
", ans);
}
int min[50010][17], max[50010][17], ansFromU[50010][17], ansToU[50010][17], p[50010][17], dep[50010];
int value[50010];
void dfs(int now, int father, int depth) {
memset(min[now], 0x3f, sizeof min[now]);
memset(max[now], 0, sizeof max[now]);
p[now][0] = father;
min[now][0] = std::min(value[now], value[p[now][0]]);
max[now][0] = std::max(value[now], value[p[now][0]]);
ansFromU[now][0] = value[now] > value[p[now][0]] ? value[now] - value[p[now][0]] : 0;
ansToU[now][0] = value[now] < value[p[now][0]] ? value[p[now][0]] - value[now] : 0;
dep[now] = depth;
for(int i = 1; i < 17; ++i) {
p[now][i] = p[p[now][i-1]][i-1];
min[now][i] = std::min(min[now][i-1], min[p[now][i-1]][i-1]);
max[now][i] = std::max(max[now][i-1], max[p[now][i-1]][i-1]);
ansFromU[now][i] = std::max(ansFromU[now][i-1], ansFromU[p[now][i-1]][i-1]);
ansFromU[now][i] = std::max(ansFromU[now][i], max[now][i-1] - min[p[now][i-1]][i-1]);
ansToU[now][i] = std::max(ansToU[now][i-1], ansToU[p[now][i-1]][i-1]);
ansToU[now][i] = std::max(ansToU[now][i], max[p[now][i-1]][i-1] - min[now][i-1]);
}
for(int i = tail[now]; i != -1; i = pre[i]) {
if(to[i] == p[now][0])
continue;
dfs(to[i], now, depth + 1);
}
}
int getLca(int u, int v) {
if(dep[u] > dep[v])
std::swap(u, v);
for(int delta = dep[v] - dep[u], i = 0; delta; delta >>= 1, ++i) {
if(delta & 1)
v = p[v][i];
}
if(u == v)
return u;
for(int i = 17 - 1; i >= 0; --i) {
if(p[u][i] == p[v][i])
continue;
u = p[u][i], v = p[v][i];
}
return p[u][0];
}
int getFromU(int u, int lca) {
int maxPre = 0, ans = 0;
for(int delta = dep[u] - dep[lca], i = 0; delta; delta >>= 1, ++i) {
if(delta & 1) {
ans = std::max(ans, ansFromU[u][i]);
ans = std::max(ans, maxPre - min[u][i]);
maxPre = std::max(maxPre, max[u][i]);
u = p[u][i];
}
}
return ans;
}
int getToU(int u, int lca) {
int minPre = 0x3f3f3f3f, ans = 0;
for(int delta = dep[u] - dep[lca], i = 0; delta; delta >>= 1, ++i) {
if(delta & 1) {
ans = std::max(ans, ansToU[u][i]);
ans = std::max(ans, max[u][i] - minPre);
minPre = std::min(minPre, min[u][i]);
u = p[u][i];
}
}
return ans;
}
int getMax(int u, int lca) {
int ret = 0;
for(int delta = dep[u] - dep[lca], i = 0; delta; delta >>= 1, ++i) {
if(delta & 1) {
ret = std::max(ret, max[u][i]);
u = p[u][i];
}
}
return ret;
}
int getMin(int u, int lca) {
int ret = 0x3f3f3f3f;
for(int delta = dep[u] - dep[lca], i = 0; delta; delta >>= 1, ++i) {
if(delta & 1) {
ret = std::min(ret, min[u][i]);
u = p[u][i];
}
}
return ret;
}
void MAIN(int n) {
for(int i = 1; i <= n; ++i)
scanf("%d", &value[i]);
getEdge(n);
dfs(1, 1, 0);
int q;
scanf("%d", &q);
for(int i = 0, u, v; i < q; ++i) {
scanf("%d%d", &u, &v);
int ans = 0, lca = getLca(u, v);
ans = std::max(ans, getToU(u, lca));
ans = std::max(ans, getFromU(v, lca));
ans = std::max(ans, getMax(v, lca) - getMin(u, lca));
printf("%d
", ans);
}
}
int main() {
int n;
while(scanf("%d", &n) > 0)
MAIN(n);
return 0;
}
트리 체인 분할 + 세그먼트 트리
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <climits>
using namespace std;
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define pb push_back
const int MAXN=33333;
struct Node{
int l,r,Min,Max,Pro[2];
}node[MAXN*6];
int f[MAXN];
int n,m;
int head[MAXN],tot;
int top[MAXN];
int fa[MAXN];
int deep[MAXN];
int num[MAXN];
int p[MAXN];
int fp[MAXN];
int son[MAXN];
int pos;
struct Seg{
void pushup(int x){
node[x].Max=max(node[lson(x)].Max, node[rson(x)].Max );
node[x].Min=min(node[lson(x)].Min, node[rson(x)].Min );
node[x].Pro[1]=max(node[lson(x)].Pro[1], node[rson(x)].Pro[1] );
node[x].Pro[1]=max(node[x].Pro[1] , node[rson(x)].Max-node[lson(x)].Min );///maybe negative!!!!
node[x].Pro[0]=max(node[lson(x)].Pro[0], node[rson(x)].Pro[0] );
node[x].Pro[0]=max(node[x].Pro[0] , node[lson(x)].Max-node[rson(x)].Min );///maybe negative!!!!
}
void build(int l,int r,int x=1){
node[x].l=l ; node[x].r=r;
if(l==r){
node[x].Max=f[fp[l]];///mind f
node[x].Min=f[fp[l]];///mind f
//cout<<l<<":"<<f[fp[l]]<<endl;
node[x].Pro[0]=0;
node[x].Pro[1]=0;
return ;
}
int mid=(l+r)/2;
build(l,mid,lson(x));
build(mid+1,r,rson(x));
pushup(x);
}
int query(int l,int r,int flag,int x=1 ){///mind !
if(l==r) return 0;
if(node[x].l >= l && node[x].r <= r){
return node[x].Pro[flag];
}
int mid=(node[x].l + node[x].r)/2;
//pushdown
int ans=-INT_MAX; ///is right?
if(l<=mid){
ans=max(ans, query(l,r ,flag,lson(x)) );
}
if(r>mid) {
ans=max(ans,query(l,r, flag,rson(x) ) );
}
if(l<=mid && r>mid){
if(flag==1){
int lMin=queryMin(l,r,lson(x)) , rMax= queryMax(l,r,rson(x));
ans=max(ans, rMax-lMin);
}else{
int lMax=queryMax(l,r,lson(x)) , rMin= queryMin(l,r,rson(x));
ans=max(ans, lMax-rMin);
}
}
pushup(x);
return ans;
}
int queryMax(int l,int r,int x=1){///mind !
if(node[x].l >= l && node[x].r <= r){
return node[x].Max;
}
int mid=(node[x].l + node[x].r)/2;
//pushdown
int ans=-INT_MAX; ///is right?
if(l<=mid) ans=max(ans, queryMax(l,r,lson(x) ) );
if(r>mid) ans=max(ans,queryMax(l,r,rson(x) ) );
pushup(x);
return ans;
}
int queryMin(int l,int r,int x=1){///mind !
if(node[x].l >= l && node[x].r <= r){
return node[x].Min;
}
int mid=(node[x].l + node[x].r)/2;
//pushdown
int ans=INT_MAX; ///is right?
if(l<=mid) ans=min(ans, queryMin(l,r,lson(x) ) );
if(r>mid) ans=min(ans,queryMin(l,r,rson(x) ) );
pushup(x);
return ans;
}
}seg;
struct Edge{
int from,to,next , w;
}edge[MAXN*5] ;
void init(){
tot=0;
memset(head,-1,sizeof(head));
pos=1;
memset(son,-1,sizeof(son));
}
void addedge(int u,int v,int w){
edge[tot].from = u;
edge[tot].to = v;
edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot++;
}
void dfs1(int u,int pre,int d){
deep[u]=d;
fa[u]=pre;
num[u]=1;
for(int i=head[u];i != -1; i=edge[i].next){
int v=edge[i].to;
if(v!=pre){
dfs1(v,u,d+1);
num[u]+=num[v];
if(son[u] == -1 || num[v] > num[ son[u] ] )
son[u]=v;
}
}
}
void getpos(int u,int sp){
top[u]=sp;
p[u]=pos++;
fp[p[u]] = u;
if(son[u]==-1) return;
getpos(son[u] , sp);
for(int i=head[u] ; i!=-1 ; i=edge[i].next){
int v=edge[i].to;
if(v!=son[u] && v!=fa[u])
getpos(v,v);
}
}
int GetQ(int u,int v){
int f1=top[u] , f2=top[v];
int tmp=0;
vector<int > ANS ;
vector<int >MAX[2] ,MIN[2];
int flag=0;
while(f1!=f2){
if(deep[f1] < deep[f2]){
swap(f1,f2);
swap(u,v);
flag^=1;
}
int ans=seg.query(p[f1],p[u] , flag ) ;
ANS.push_back(ans);
MAX[flag].push_back(seg.queryMax(p[f1],p[u]) );
MIN[flag].push_back(seg.queryMin(p[f1],p[u]) );
u=fa[f1];
f1=top[u];
}
if(deep[u] > deep[v] ) swap(u,v) ;
else flag^=1;
int ans=seg.query(p[u], p[v] ,flag) ;
//cout<<p[u]<<" "<<p[v]<<" "<<flag<<endl;
ANS.push_back(ans);
if(ANS.size()==1) return ANS[0];
MAX[flag].push_back(seg.queryMax(p[u], p[v]) );
MIN[flag].push_back(seg.queryMin(p[u], p[v]) );
int lastres=ANS[0];
for(int i=MAX[1].size()-1 ; i>=0 ; i--){
MAX[0].pb(MAX[1][i]);
MIN[0].pb(MIN[1][i]);
}
int minn=MIN[0][0];
for(int i=1; i<ANS.size() ; i++){
lastres=max(lastres,ANS[i]);
lastres=max(lastres,MAX[0][i]-minn);
minn=min(minn,MIN[0][i]);
}
return lastres;
}
struct Bing{
int par[MAXN];
void init(int n){
for(int i=1;i<=n;i++) par[i]=i;
}
int find(int u){
if(par[u]==u) return u;
else return par[u]=find(par[u]);
}
void unite(int u,int v){
u=find(u);
v=find(v);
if(u==v) return;
par[u]=v;
}
}bing;
bool cmp(const Edge& e1,const Edge& e2){
return e1.w < e2.w;
}
int kruskal(int edgeNum , vector<pair<int ,int > >& newG ){
sort(edge,edge+edgeNum,cmp);
bing.init(n);
int res=0;
for(int i=0;i<edgeNum;i++){
Edge e=edge[i];
if(bing.find(e.from ) != bing.find(e.to ) ){
bing.unite(e.from , e.to);
newG.push_back(make_pair(e.from, e.to) );
res+=e.w;
}
}
return res;
}
int main()///mind lld??
{
//freopen("in.txt","r",stdin);
while(scanf("%d",&n)==1)
{
init();
for(int i=1;i<=n;i++) scanf("%d",&f[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
w=-w;
addedge(u,v,w);
addedge(v,u,w);
}
vector<pair<int ,int > > newG;
int sum=kruskal(tot,newG);
sum=-sum;
printf("%d
",sum);
tot=0;
memset(head,-1,sizeof(head));
for(int i=0;i<newG.size(); i++){
int u=newG[i].first ,v=newG[i].second;
addedge(u,v,0);
addedge(v,u,0);
}
dfs1(1,0,0);
getpos(1,1);
seg.build(1,pos-1);
//cout<<seg.query(5,6,0)<<endl;
int que;
scanf("%d",&que);
while(que--){
int u,v;
scanf("%d%d",&u,&v);
int ans=GetQ(u,v);
printf("%d
",ans);
}
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
