cf-788 B区間図が一番短絡します.
15409 ワード
https://www.cnblogs.com/31415926535x/p/11611801.html 偶然に見たこのものは、初めて図面＋データ構造の問題を見たと言えます.この問題はコードが簡単で、細かいところで処理すれば大丈夫です.
cf-756レガシー
cf-756レガシー
以前作った図論題はただ図論題だけで、データ構造の線分樹と関係があるとは考えられませんでした.
この問題は経典の例題とも言えるでしょう.知っているようにして作られるタイプです.
考え方の分析
題意は簡単です.つまり、簡単な図です.いくつかの図面を提供します.しかし、以前と違って、以前の辺の関係は点と点の関係です.この問題は区間です.例えば
思いつきやすい方法は、直接に二つのforを上にして、それぞれの辺を作って、データが小さい時は大丈夫ですが、nが大きい時は、明らかに図の複雑さは\((O(n^2 m)\)かもしれません.
最適化の方法の一つは、私達がこの二つの区間の間に一つの点を加えて、前の区間と後ろの区間(入区間と呼ぶ)がこの点とつながっています.つまり、\(\forall u\n[l_1]:addedge(u,p,w)は、(\forall l[udge])[/udv]、(\u])[/del]、[/dl]、[/udv]、[/udl]、[/uddl]、((([udl]])[/udl]]]、[/udl]、[/udl]]、[/udl]、((((([/udl]))))))))[/udl]、[/udl]]、[/u_2,r_2\)このように一次元の建設図を下げることができます.複雑さは\(O(2 nm)\)ですが、それでも高いです.
この時の建図はリニアの建図方式で、リニア+区間==線分樹?!これは私がこの問題をやって学んだ最も価値のある処理方法です.一次元を落とした後、線形の建設図ですが、点はまだ多いです.線分樹はちょうど少ない分区間で元の区間を表します.線分樹の各表示区間を一つの点と見なすと、少ない点で図を作ることができます.このようにして上のn回の建設図を下に下げることができます.
この時の問題は線分樹をどうやって処理しますか?
私たちは2本の線分の木が必要です.1本は入木した別の1本を木のように見ています.
まず、私達の目的は少量の区間で元の大きな区間を表して、少ない点で元のすべての点を表します.最適化の問題は線分樹で解決しました.しかし、元のすべての点をどのように正確に表しますか?
線分樹の各ノードは一つの区間を表しています.このノードは彼の下のすべての点を表してもいいです.つまり、私達は上から下を見てもいいです.定義は一つのノードを選んだので、次のすべての点を選択しました.入木中のすべての端が下を指し、
同じように、ツリーを出すには、ノードがすべての点を示すことができることを保証します.したがって、ノードの下のすべてのノードがそれを指します.このように見ると、この木は上向きの木です.
このような
このように最後にこのような初期図に問題が与えられたいくつかの条件を加えて走りながら一番短絡すればいいです.
タイトルの端を足した図は大体こんな感じです.
実際には、ここの線分樹の役割はただ一つの建樹とそのサブ区間の役割を調べるだけで、この思想は少しブロックに分けられているようです.合理的な区間を見つけてブロックを分けて、いくつかの合理的な、数量の少ない区間で元の区間を表して、点数を減らす役割を果たすことができます.操作の良い区間は模型を区分していますので、多くの人が区間図の最短の問題に対して線分樹をセットした板です.
この問題に戻りますと、テーマのプラス側の方式は区間と区間の2種類しかないです.だから、まずそのn個の点を残しておいてもいいです.この2本の木の間に置いた一列の点を想像できます.
次に、ツリーを取り出し、ツリーのエッジを処理した後、
同じ理由で
最後に最も短絡を走って、前のn個の点の
そこで、私達は辺を少し減らして、図を作る時間の複雑さを減らしました.
ツリーを処理して、ツリーに入る操作、つまり線分樹の樹立過程については、実は線分樹は何の情報も守られていません.私たちは自分の各ノードで一つの区間という自身の性質を表しています.つまり、各ノードの番号を一つの
最後のコード:
最後のACコードの大体の考えはヒョウタンじいさんの板を参考にします.
hdu-5361 In Touch
hdu-5361 In Touch
大体の問題は解法が多いようです.この方法で解けば、一本の木に入ればいいです.また、書き換えの姿勢を変えなければならないかもしれません.
AC_1
(速く読まなくても大丈夫です.つまり、memsetはだめです.、カードmsetは気持ちが悪いです.
cf-756レガシー
cf-756レガシー
以前作った図論題はただ図論題だけで、データ構造の線分樹と関係があるとは考えられませんでした.
この問題は経典の例題とも言えるでしょう.知っているようにして作られるタイプです.
考え方の分析
題意は簡単です.つまり、簡単な図です.いくつかの図面を提供します.しかし、以前と違って、以前の辺の関係は点と点の関係です.この問題は区間です.例えば
u->[l, r]はuとこの区間のすべての点に辺があります.一つの点は自分だけの区間とも見られますので、このような関係を統一して見てもいいです.思いつきやすい方法は、直接に二つのforを上にして、それぞれの辺を作って、データが小さい時は大丈夫ですが、nが大きい時は、明らかに図の複雑さは\((O(n^2 m)\)かもしれません.
最適化の方法の一つは、私達がこの二つの区間の間に一つの点を加えて、前の区間と後ろの区間(入区間と呼ぶ)がこの点とつながっています.つまり、\(\forall u\n[l_1]:addedge(u,p,w)は、(\forall l[udge])[/udv]、(\u])[/del]、[/dl]、[/udv]、[/udl]、[/uddl]、((([udl]])[/udl]]]、[/udl]、[/udl]]、[/udl]、((((([/udl]))))))))[/udl]、[/udl]]、[/u_2,r_2\)このように一次元の建設図を下げることができます.複雑さは\(O(2 nm)\)ですが、それでも高いです.
この時の建図はリニアの建図方式で、リニア+区間==線分樹?!これは私がこの問題をやって学んだ最も価値のある処理方法です.一次元を落とした後、線形の建設図ですが、点はまだ多いです.線分樹はちょうど少ない分区間で元の区間を表します.線分樹の各表示区間を一つの点と見なすと、少ない点で図を作ることができます.このようにして上のn回の建設図を下に下げることができます.
この時の問題は線分樹をどうやって処理しますか?
私たちは2本の線分の木が必要です.1本は入木した別の1本を木のように見ています.
まず、私達の目的は少量の区間で元の大きな区間を表して、少ない点で元のすべての点を表します.最適化の問題は線分樹で解決しました.しかし、元のすべての点をどのように正確に表しますか?
線分樹の各ノードは一つの区間を表しています.このノードは彼の下のすべての点を表してもいいです.つまり、私達は上から下を見てもいいです.定義は一つのノードを選んだので、次のすべての点を選択しました.入木中のすべての端が下を指し、
downで表される.同じように、ツリーを出すには、ノードがすべての点を示すことができることを保証します.したがって、ノードの下のすべてのノードがそれを指します.このように見ると、この木は上向きの木です.
upで表します.このような
このように最後にこのような初期図に問題が与えられたいくつかの条件を加えて走りながら一番短絡すればいいです.
タイトルの端を足した図は大体こんな感じです.
実際には、ここの線分樹の役割はただ一つの建樹とそのサブ区間の役割を調べるだけで、この思想は少しブロックに分けられているようです.合理的な区間を見つけてブロックを分けて、いくつかの合理的な、数量の少ない区間で元の区間を表して、点数を減らす役割を果たすことができます.操作の良い区間は模型を区分していますので、多くの人が区間図の最短の問題に対して線分樹をセットした板です.
この問題に戻りますと、テーマのプラス側の方式は区間と区間の2種類しかないです.だから、まずそのn個の点を残しておいてもいいです.この2本の木の間に置いた一列の点を想像できます.
次に、ツリーを取り出し、ツリーのエッジを処理した後、
u->[l, r]とu->vの辺について、ポイントuから入木の条件に合致するノードに隣接すればいいです.前に言った入木は各ノードがその下の葉っぱノードに到達することができることを保証していますので、私たちのこのような辺続きは点uから区間の各点につながっています. 同じ理由で
[l, r]->uのような辺については、入木の対応するノードと点uとを接続し、このようにして、入木中のこの区間の葉っぱノードがこれらの区間を通じて点uに到達できることを保証し、このようにしても、題意を満たしながら減少するエッジの複雑さ、最後に最も短絡を走って、前のn個の点の
dis[i]は源図のあれらの点のために最も短絡して、そこで、私達は辺を少し減らして、図を作る時間の複雑さを減らしました.
ツリーを処理して、ツリーに入る操作、つまり線分樹の樹立過程については、実は線分樹は何の情報も守られていません.私たちは自分の各ノードで一つの区間という自身の性質を表しています.つまり、各ノードの番号を一つの
id[rt]でマークすればいいです.最後のコード:
#include
#define aaa cout<<233< 1e9
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 1e6 + 5;
const int maxm = 1e7 + 233;
const int mod = 1e9 + 7;
struct Dijkstra
{
struct edge
{
int to, nxt; ll w;
}edge[maxm];
int tot, head[maxm];
void init()
{
tot = 0;
memset(head, -1, sizeof head);
}
void addedge(int u, int v, ll w)
{
edge[tot].to = v;
edge[tot].w = w;
edge[tot].nxt = head[u];
head[u] = tot++;
}
struct node
{
int v; ll w;
node(){}
node(int _v, ll _w):v(_v), w(_w){}
const bool operator r.w;
}
};
bool vis[maxn];
ll dis[maxn];
priority_queue pq;
void dijkstra(int s, int n)
{
memset(vis, false, sizeof vis);
memset(dis, inf, sizeof dis);
while(!pq.empty())pq.pop();
pq.push(node(s, 0));
dis[s] = 0;
node t;
int u;
while(!pq.empty())
{
t = pq.top(); pq.pop();
u = t.v;
if(vis[u])continue;
vis[u] = true;
for(int i = head[u]; ~i; i = edge[i].nxt)
{
int v = edge[i].to;
ll w = edge[i].w;
if(dis[v] > t.w + w)
{
dis[v] = t.w + w;
pq.push(node(v, dis[v]));
}
}
}
}
void print(int n)
{
for(int i = 1; i <= n; ++i)cout << (dis[i] == linf ? -1 : dis[i]) << " ";cout << endl;
}
}dijkstra;
int cnt;
struct segmentTree
{
int id[maxn]; // ，， ，， n+1 ，， n
void build(int rt, int l, int r, bool flag) // （ ，，flag == false ， ，
{
id[rt] = ++cnt;
if(l == r)
{
int u = id[rt];
int v = l;
if(flag)swap(u, v);
dijkstra.addedge(u, v, 0);
return;
}
int mid = l + r >> 1;
build(rt << 1, l, mid, flag);
build(rt << 1 | 1, mid + 1, r, flag);
// pushup
int u = id[rt];
int v = id[rt << 1];
if(flag)swap(u, v);
dijkstra.addedge(u, v, 0);
u = id[rt];
v = id[rt << 1 | 1];
if(flag)swap(u, v);
dijkstra.addedge(u, v, 0);
return;
}
void addedge(int rt, int l, int r, int U, int L, int R, ll w, bool flag) // flag == false u->[l, r] ，，
{
if(l > R || L > r)return;
if(L <= l && r <= R)
{
int u = U;
int v = id[rt];
if(flag)swap(u, v);
dijkstra.addedge(u, v, w);
return;
}
int mid = l + r >> 1;
if(L <= mid)addedge(rt << 1, l, mid, U, L, R, w, flag);
if(R > mid)addedge(rt << 1 | 1, mid + 1, r, U, L, R, w, flag);
return;
}
}down, up;
int main()
{
// double pp = clock();
// freopen("233.in", "r", stdin);
// freopen("233.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n, q, s;
cin >> n >> q >> s;
cnt = n; // 、 n+1
dijkstra.init();
down.build(1, 1, n, false);
up.build(1, 1, n, true);
int t, u, v, w, l, r;
while(q--)
{
cin >> t;
if(t == 1)
{
cin >> u >> v >> w;
l = r = v;
t = 2;
}
else
cin >> u >> l >> r >> w;
if(t == 2)
down.addedge(1, 1, n, u, l, r, w, false); // u -> [l, r]
else
up.addedge(1, 1, n, u, l, r, w, true); // [l, r] -> u
}
dijkstra.dijkstra(s, cnt);
dijkstra.print(n);
// cout << endl << (clock() - pp) / CLOCKS_PER_SEC << endl;
return 0;
} 最後のACコードの大体の考えはヒョウタンじいさんの板を参考にします.
hdu-5361 In Touch
hdu-5361 In Touch
大体の問題は解法が多いようです.この方法で解けば、一本の木に入ればいいです.また、書き換えの姿勢を変えなければならないかもしれません.
AC_1
#include
// #include
// #include
// #include
#define aaa cout<<233< 1e9
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 2e5 + 5;
const int maxm = 1e7 + 233;
const int mod = 1e9 + 7;
inline int read() //
{
int ans=0;
char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch))
ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n;
struct edge
{
int to, nxt;
ll w;
}edge[maxm];
int tot, head[maxn << 3];
void init(int n)
{
tot = 0;
for(int i = 0; i <= n; ++i)head[i] = -1;
}
void ADDEDGE(int u, int v, ll w)
{
edge[tot].to = v;
edge[tot].w = w;
edge[tot].nxt = head[u];
head[u] = tot++;
}
struct node
{
int v;
ll w;
node(){};
node(int _v, ll _w): v(_v), w(_w){};
const bool operator r.w;
}
}tmp;
bool vis[maxn << 3];
ll dis[maxn << 3];
priority_queue pq;
void dijkstra(int s, int n)
{
for(int i = 0; i <= n; ++i)dis[i] = linf;
for(int i = 0; i <= n; ++i)vis[i] = false;
while(!pq.empty())pq.pop();
pq.push(node(s, 0));
dis[s] = 0;
while(!pq.empty())
{
tmp = pq.top(); pq.pop();
if(vis[tmp.v])continue;
vis[tmp.v] = true;
for(int i = head[tmp.v]; ~i; i = edge[i].nxt)
{
int v = edge[i].to;
if(dis[v] > dis[tmp.v] + edge[i].w)
{
dis[v] = dis[tmp.v] + edge[i].w;
pq.push(node(v, dis[v]));
}
}
}
}
int cnt;
void build(int rt, int l, int r)
{
if(l == r)
{
cnt = max(cnt, rt + n);
ADDEDGE(rt + n, l, 0);
return;
}
int mid = l + r >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
ADDEDGE(rt + n, (rt << 1) + n, 0);
ADDEDGE(rt + n, (rt << 1 | 1) + n, 0);
}
int L, R, W, U;
void addedge(int rt, int l, int r)
{
if(L > r || l > R)return;
if(L <= l && r <= R)
{
ADDEDGE(U, rt + n, W);
return;
}
int mid = l + r >> 1;
if(L <= mid)addedge(rt << 1, l, mid);
if(R > mid)addedge(rt << 1 | 1, mid + 1, r);
}
int l[maxn], r[maxn], c[maxn];
int main()
{
// double pp = clock();
// freopen("233.in", "r", stdin);
// freopen("233.out", "w", stdout);
// ios_base::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// int t; cin >> t;
// int t; scanf("%d", &t);
int t; t = read();
while(t--)
{
// cin >> n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i)l[i] = read();
for(int i = 1; i <= n; ++i)r[i] = read();
for(int i = 1; i <= n; ++i)c[i] = read();
init(n << 3);
cnt = 0;
build(1, 1, n);
for(int i = 1; i <= n; ++i)
{
U = i;
L = i + l[i]; R = i + r[i]; W = c[i];
addedge(1, 1, n);
L = i - r[i]; R = i - l[i];
addedge(1, 1, n);
}
dijkstra(1, cnt);
printf("0");
for(int i = 2; i <= n; ++i)
printf(" %lld", (dis[i] == linf ? -1 : dis[i]));
puts("");
}
// cout << endl << (clock() - pp) / CLOCKS_PER_SEC << endl;
return 0;
} (速く読まなくても大丈夫です.つまり、memsetはだめです.、カードmsetは気持ちが悪いです.
#include
#define aaa cout<<233< 1e9
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 2e5 + 5;
const int maxm = 1e7 + 233;
const int mod = 1e9 + 7;
inline int read() //
{
int ans=0;
char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch))
ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
struct Dijkstra
{
struct edge
{
int to, nxt;
ll w;
}edge[maxm];
int tot, head[maxn << 3];
void init(int n)
{
tot = 0;
// memset(head, -1, sizeof head);
for(int i = 0; i <= n; ++i)head[i] = -1;
}
void addedge(int u, int v, ll w)
{
edge[tot].to = v;
edge[tot].w = w;
edge[tot].nxt = head[u];
head[u] = tot++;
}
struct node
{
int v; ll w;
node(){}
node(int _v, ll _w):v(_v), w(_w){}
const bool operator r.w;
}
};
bool vis[maxn << 3];
ll dis[maxn << 3];
priority_queue pq;
void dijkstra(int s, int n)
{
// memset(vis, false, sizeof vis);
// memset(dis, inf, sizeof dis);
for(int i = 0; i <= n; ++i)vis[i] = false;
for(int i = 0; i <= n; ++i)dis[i] = linf;
while(!pq.empty())pq.pop();
pq.push(node(s, 0));
dis[s] = 0;
node t; int u;
while(!pq.empty())
{
t = pq.top(); pq.pop();
u = t.v;
if(vis[u])continue;
vis[u] = true;
for(int i = head[u]; ~i; i = edge[i].nxt)
{
int v = edge[i].to;
ll w = edge[i].w;
if(dis[v] > t.w + w)
{
dis[v] = t.w + w;
pq.push(node(v, dis[v]));
}
}
}
}
void print(int n)
{
printf("0");
for(int i = 2; i <= n; ++i)printf(" %lld", (dis[i] == linf ? -1 : dis[i]));
puts("");
}
}dijkstra;
int cnt;
struct segmentTree
{
int id[maxn << 3];
void build(int rt, int l, int r, bool flag)
{
id[rt] = ++cnt;
if(l == r)
{
int u = id[rt];
int v = l;
if(flag)swap(u, v);
dijkstra.addedge(u, v, 0);
return;
}
int mid = l + r >> 1;
build(rt << 1, l, mid, flag);
build(rt << 1 | 1, mid + 1, r, flag);
int u = id[rt];
int v = id[rt << 1];
if(flag)swap(u, v);
dijkstra.addedge(u, v, 0);
u = id[rt];
v = id[rt << 1 | 1];
if(flag)swap(u, v);
dijkstra.addedge(u, v, 0);
return;
}
void addedge(int rt, int l, int r, int U, int L, int R, ll w, bool flag)
{
if(L > r || R < l)return;
if(L <= l && r <= R)
{
int u = U;
int v = id[rt];
if(flag)swap(u, v);
dijkstra.addedge(u, v, w);
return;
}
int mid = l + r >> 1;
if(L <= mid)addedge(rt << 1, l, mid, U, L, R, w, flag);
if(R > mid)addedge(rt << 1 | 1, mid + 1, r, U, L, R, w, flag);
return;
}
}down; //, up;
int l[maxn], r[maxn], c[maxn];
int main()
{
// double pp = clock();
// freopen("233.in", "r", stdin);
// freopen("233.out", "w", stdout);
// ios_base::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
int t; t = read();
while(t--)
{
int n; n = read();
for(int i = 1; i <= n; ++i)l[i] = read();
for(int i = 1; i <= n; ++i)r[i] = read();
for(int i = 1; i <= n; ++i)c[i] = read();
cnt = n;
dijkstra.init(n << 3);
down.build(1, 1, n, false);
// up.build(1, 1, n, true);
for(int i = 1; i <= n; ++i)
{
down.addedge(1, 1, n, i, l[i] + i, r[i] + i, c[i], false);
down.addedge(1, 1, n, i, max(1, i - r[i]), max(1, i - l[i]), c[i], false);
}
dijkstra.dijkstra(1, cnt);
dijkstra.print(n);
}
// cout << endl << (clock() - pp) / CLOCKS_PER_SEC << endl;
return 0;
}