Dylan's Blog
0%

Posted on Edited on In

问题描述

FJ的农场周围分布着N(1<=N<=1,000)根按1..N顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P(1<=P<=10,000)对电话线杆间可以拉电话线。第i对电话线杆的两个端点分别为A_i、B_i，它们间的距离为L_i(1<=L_i<=1,000,000)。数据中保证每对{A_i，B_i}最多只出现1次。 FJ的任务仅仅是找一条将1号和N号电话线杆连起来的路径，其余的电话线杆并不一定要连入电话网络。经过谈判，电信公司最终同意免费为FJ连结K(0<=K<N)对由FJ指定的电话线杆。对于此外的那些电话线，FJ需要为它们付的费用，等于其中最长的电话线的长度（每根电话线仅连结一对电话线杆）。如果需要连结的电话线杆不超过K对，那么FJ的总支出为0。 请你计算一下，FJ最少需要在电话线上花多少钱。

输入

第1行: 3个用空格隔开的整数：N，P，以及K 第2..P+1行: 第i+1行为3个用空格隔开的整数：A_i，B_i，L_i

输出

第1行: 输出1个整数，为FJ在这项工程上的最小支出。 如果任务不可能完成， 输出-1

思路

一般求“最大的最小值”或“最小的最大值”都很容易想到二分。这道题求的是第K+1大的最小值，所以也同样可以使用二分。

我们二分答案，设当前二分的答案为x。此时最大的边权<=x，显然当边的权值大于x时，这条边就应该免费。判断此时是否符合要求就只需要判断到达n节点时经过免费的边数是否大于k。

我们可以用SPFA来处理到达n节点时经过最少的免费边数。如果一条边的权值大于x，就设它的距离为1，否则为0。如果到n点的距离<=k，就是符合要求的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define MAXN 1005
#define MAXE 10005
using namespace std;

struct Edge {int next, to, dis;} edge[MAXE*2];

int n, m, k, a, b, c, cnt, ans=-1, dis[MAXN], head[MAXN];
bool vis[MAXN];

void addedge(int from, int to, int dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

bool check(int lim)
{
    queue<int> q;
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    vis[1]=true; dis[1]=0;
    q.push(1);
    while(!q.empty())
    {
        int x=q.front(); q.pop();
        vis[x]=false;
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            int d=(edge[i].dis>lim);
            if(dis[x]+d<dis[to])
            {
                dis[to]=dis[x]+d;
                if(vis[to]) continue;
                vis[to]=true;
                q.push(to);
            }
        }
    }
    return dis[n]<=k;
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        addedge(a, b, c);
        addedge(b, a, c);
    }
    int l=0, r=1000000;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))  ans=mid, r=mid-1;
        else l=mid+1;
    }
    printf("%d\n", ans);
}

Posted on Edited on In

问题描述

大意就是给了你一棵树，你可以选任意节点作为根节点。根节点为源点，所有叶子节点为汇点，求出最大流。

输入

第一行T，表示T组数据。 每组数据第一行为n (n<=200005),表示有n个节点，接下来n-1行描述每一条边的端点和流量，

输出

每一组数据输出一个数字，为该组数据的最大流量。

思路

暴力枚举每一个顶点作为源点的n^2做法应该不难想到。然后在《算法进阶指南》上学到了O(n)的高级操作(二次扫描与换根法)。

我们任选一个节点作为源点。先扫描一遍，处理从出每个节点出发流向子树的最大流量。然后再扫描一遍，可以处理出每个点作为源点的最大流。

第一遍扫描可以用一个简单的DP解决，第i个点的最大流量储存为f[i]。第二遍扫描时可以利用已经处理好的f数组，推出每个点的答案，第i个点的答案储存为g[i]。我们从根节点开始dfs，设当前节点为x，它的子节点为y，从x流向除y以外其余部分的流量可以表示为g[x]-min(f[y], flow(x, y))，所以g[y]=min(g[x]-min( f[y], flow(x, y))，flow(x, y) )+f[y]。

细节

  1. 当求f[i],和g[i]时，若i节点度数为1要注意特判！！！
  2. 式子中的变量不要弄混了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 200005
using namespace std;

struct Edge {int next, to, flow;} edge[MAXN*2];

int T, n, x, y, z, ans, cnt, f[MAXN], g[MAXN], deg[MAXN], head[MAXN];

void addedge(int from, int to, int flow)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].flow=flow;
    deg[to]++;
    head[from]=cnt;
}

void init()
{
    memset(edge, 0, sizeof(edge));
    for(int i=1; i<MAXN; i++)
        f[i]=g[i]=head[i]=deg[i]=0;
    cnt=ans=0;
}

void dfs1(int x, int fa)
{
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dfs1(to, x);
        if(deg[to]==1) f[x]+=edge[i].flow;
        else f[x]+=min(f[to], edge[i].flow);
    }
}

void dfs2(int x, int fa)
{
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        if(deg[x]==1) g[to]=f[to]+edge[i].flow;
        else g[to]=f[to]+min(g[x]-min(f[to], edge[i].flow), edge[i].flow);
        dfs2(to, x);
    }
    ans=max(ans, g[x]);
}


int main()
{
    scanf("%d", &T);
    while(T--)
    {
        init();
        scanf("%d", &n);
        for(int i=1; i<n; i++)
        {
            scanf("%d%d%d", &x, &y, &z);
            addedge(x, y, z);
            addedge(y, x, z);
        }
        dfs1(1, 0);
        g[1]=f[1];
        dfs2(1, 0);
        printf("%d\n", ans);
    }
}

Posted on Edited on In

问题描述

你在一家 IT 公司为大型写字楼或办公楼（offices）的计算机数据做备份。然而数据备份的工作是枯燥乏味的，因此你想设计一个系统让不同的办公楼彼此之间互相备份，而你则坐在家中尽享计算机游戏的乐趣。

已知办公楼都位于同一条街上。你决定给这些办公楼配对（两个一组）。每一对办公楼可以通过在这两个建筑物之间铺设网络电缆使得它们可以互相备份。然而，网络电缆的费用很高。当地电信公司仅能为你提供 K 条网络电缆，这意味着你仅能为 K 对办公楼（或总计2K个办公楼）安排备份。任一个办公楼都属于唯一的配对组（换句话说，这 2K 个办公楼一定是相异的）。此外，电信公司需按网络电缆的长度（公里数）收费。

因而，你需要选择这 K 对办公楼使得电缆的总长度尽可能短。换句话说，你需要选择这 K 对办公楼，使得每一对办公楼之间的距离之和（总距离）尽可能小。

输入

第一行包含整数n和k。 其中n（2≤n≤100000）表示办公楼的数目，k（1≤k≤n/2）表示可利用的网络电缆的数目。

接下来的n行每行仅包含一个整数（0≤s≤1000000000）,表示每个办公楼到大街起点处的距离。这些整数将按照从小到大的顺序依次出现。

输出

输出应由一个正整数组成，给出将2K个相异的办公楼连成k对所需的网络电缆的最小总长度。

思路

第一眼看题，想着用网络流去做QWQ。

想了一下后，突然想起一道题BZOJ2151 种树。当时做这道题时觉得这道题的思路十分巧妙。然后这道题也可以用一模一样的思路去做。

每次贪心选取最大值，答案加上这个最大值，最大值左右两边当然不能再选，于是就标记为访问过。

但是这个贪心显然是不完善的。当最大值左右两边之和大于它本身时，就会产生错误。于是就有一种神奇的操作：将左右两边之和减去最大值，作为新的节点，覆盖掉原来的最大值，并删去左右两个节点。

原因是要么选最大值，要么选它的左右之和，选最大值时答案加上这个最大值，不再去选新的节点，选左右之和时答案还是加上最大值，只不过后面还要加上新节点的值。也就是当我们再次选取的新节点时，也就相当于选取当时最大值的左右之和，而没有选最大值。

细节

  1. 要注意链头和链尾要特殊处理；
  2. 要注意删除操作的顺序;
  3. 访问过的节点dis要标记为INF.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#define LL long long
#define INF 0x7fffffff
#define MAXN 100005
using namespace std;

struct Sec
{
    LL dis, pos;
    bool operator < (const Sec &x) const
    {
        return dis>x.dis;
    }
} sec[MAXN];

LL n, k, ans, x[MAXN], dis[MAXN], pre[MAXN], nxt[MAXN];

priority_queue<Sec> q;

int main()
{
    scanf("%lld%lld", &n, &k);
    for(int i=1; i<=n; i++) scanf("%lld", &x[i]);
    for(int i=2; i<=n; i++)
    {
        dis[i]=x[i]-x[i-1];
        q.push((Sec) {dis[i], i});
        pre[i]=i-1; nxt[i]=i+1;
    }
    pre[2]=0; nxt[n]=0;
    for(int i=1; i<=k; i++)
    {
        while(dis[q.top().pos]==INF) q.pop();
        LL pos=q.top().pos; q.pop();
        ans+=dis[pos];
        if(!nxt[pos]) //处理链尾
        {
            dis[pre[pos]]=INF;
            nxt[pre[pos]]=0;
            continue;
        }
        if(!pre[pos]) //处理链头
        {
            dis[nxt[pos]]=INF;
            pre[nxt[pos]]=0;
            continue;
        }
        dis[pos]=dis[pre[pos]]+dis[nxt[pos]]-dis[pos];
        dis[pre[pos]]=dis[nxt[pos]]=INF;
        pre[pos]=pre[pre[pos]];
        nxt[pos]=nxt[nxt[pos]];
        pre[nxt[pos]]=nxt[pre[pos]]=pos;
        q.push((Sec){dis[pos], pos});
    }
    printf("%lld\n", ans);
}

Posted on Edited on In

问题描述

你要解决软件包之间的依赖问题。如果软件包A依赖软件包B，那么安装软件包A以前，必须先安装软件包B。同时，如果想要卸载软件包B，则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除0号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而0号软件包不依赖任何一个软件包。依赖关系不存在环（若有m(m≥2)个软件包A1,A2,A3,…,Am，其中A1依赖A2，A2依赖A3，A3依赖A4，……，Am−1依赖Am，而Am依赖A1，则称这m个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。

现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为0。

输入

第1行包含1个整数n，表示软件包的总数。软件包从0开始编号。随后一行包含n−1个整数，相邻整数之间用单个空格隔开，分别表示1,2,3,⋯,n−2,n−1号软件包依赖的软件包的编号。

接下来一行包含1个整数q，表示询问的总数。之后q行，每行1个询问。询问分为两种： install x：表示安装软件包x uninstall x：表示卸载软件包x 你需要维护每个软件包的安装状态，一开始所有的软件包都处于未安装状态。

对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）

输出

输出文件包括q行。

输出文件的第i行输出1个整数，为第i步操作中改变安装状态的软件包数。

数据范围

对于全部数据：n<=100000, q<=100000。

思路

我们可以看出这些软件的依赖关系是一棵树。设未安装的节点权值为0，安装的权值为1。

然后install操作就是让x节点到根节点路径上权值为0的节点变为1，并输出权值为0节点个数。uninstall操作就是让x子树权值为1的节点变为0，并输出权值为1节点个数。

然后这就是一个很裸的树剖啦QVQ 线段树上的操作就是将整个区间变为0或1。

但是要注意常数问题！以install操作为例，如果先计算x到根节点权值之和，然后进行修改，再求一遍到根节点之和。这样的常数巨大，在BZOJ上会TLE。QWQ

所以我们可以优化一下,先保存一下整棵树权值之和(就是sum[1])，然后修改，输出整棵树前后权值之差。这样常数就小了不少。

细节

  1. 所有点的编号都要+1，不然树剖时会产生与0号节点有关的bug。
  2. lazytag要注意，初始赋为-1，下传标记时新tag要覆盖掉原tag。
  3. 要注意常数，TLE了一次QWQ

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
#define MAXN 100005
#define INF 1e9
#define ls (l+r<<1)
#define rs (l+r<<1|1)
#define mid (l+r>>1)
using namespace std;

int n, x, q, cnt, head[MAXN], tag[MAXN*4], sum[MAXN*4];
int Index, son[MAXN], f[MAXN], dep[MAXN], size[MAXN], id[MAXN], top[MAXN];
char opt[100];
struct Edge {int next, to;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void dfs1(int x, int fa, int deep)
{
    dep[x]=deep; f[x]=fa; size[x]=1;
    int maxson=-1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dfs1(to, x, deep+1);
        size[x]+=size[to];
        if(size[to]>maxson) maxson=size[to], son[x]=to;
    }
}

void dfs2(int x, int topf)
{
    id[x]= ++Index; top[x]=topf;
    if(!son[x]) return;
    dfs2(son[x], topf);
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==son[x] || to==f[x]) continue;
        dfs2(to, to);
    }
}

void down(int root, int l, int r)
{
    if(tag[root]==-1) return;
    sum[ls]=(mid-l+1)*tag[root];
    sum[rs]=(r-mid)*tag[root];
    tag[ls]=tag[root];
    tag[rs]=tag[root];
    tag[root]=-1;
}

void update(int root, int l, int r, int x, int y, int z)
{
    if(x>r || y<l) return ;
    if(x<=l && y>=r)
    {
        sum[root]=(r-l+1)*z;
        tag[root]=z;
        return;
    }
    down(root, l, r);
    update(ls, l, mid, x, y, z);
    update(rs, mid+1, r, x, y, z);
    sum[root]=sum[ls]+sum[rs];
}

void act(int x, int y)
{
    while(top[x]!=1)
    {
        update(1, 1, n, id[top[x]], id[x], y);
        x=f[top[x]];
    }
    update(1, 1, n, id[1], id[x], y);
}

int main()
{
    memset(tag, -1, sizeof(-1));
    scanf("%d", &n);
    for(int i=2; i<=n; i++)
    {
        scanf("%d", &x);
        addedge(i, x+1); 
        addedge(x+1, i);
    }
    dfs1(1, 0, 1);
    dfs2(1, 1);
    scanf("%d", &q);
    for(int i=1; i<=q; i++)
    {
        scanf("%s%d", opt, &x); x++;
        int temp=sum[1];
        if(opt[0]=='i')
        {
            act(x, 1);
            printf("%dn", sum[1]-temp);
        }
        if(opt[0]=='u')
        {
            update(1, 1, n, id[x], id[x]+size[x]-1, 0);
            printf("%dn", temp-sum[1]);
        }
    }
}