Dylan's Blog
0%

Posted on Edited on In

问题描述

Farmer John想把牛奶送到T个城镇 (1 <= T <= 25,000)，编号为1-T。这些城镇之间通过R条道路 (1 <= R <= 50,000，编号为1到R) 和P条航线 (1 <= P <= 50,000，编号为1到P) 连接。每条道路i或者航线i连接城镇A_i (1 <= A_i <= T)到B_i (1 <= B_i <= T)，花费为C_i。 对于道路，0 <= C_i <= 10,000;然而航线的花费很神奇，花费C_i可能是负数(-10,000 <= C_i <= 10,000)。道路是双向的，可以从A_i到B_i，也可以从B_i到A_i，花费都是C_i。然而航线与之不同，只可以从A_i到B_i。 如果有一条航线可以从A_i到B_i，那么保证不可能通过一些道路和航线从B_i回到A_i。他需要运送奶牛到每一个城镇。他想找到从发送中心城镇S(1 <= S <= T) 把奶牛送到每个城镇的最便宜的方案，或者知道这是不可能的。

输入

第1行：四个空格隔开的整数: T, R, P, and S 第2到R+1行：三个空格隔开的整数（表示一条道路）：A_i, B_i 和C_i 第R+2到R+P+1行：三个空格隔开的整数（表示一条航线）：A_i, B_i 和 C_i

输出

第1到T行：从S到达城镇i的最小花费，如果不存在输出”NO PATH”。

思路

最早一看以为是一个裸的SPFA，于是很愉快的花十分钟码完了，结果T了两个点。果然BZOJ没有这么水的题QWQ原来数据构造好了要卡SPFA。

正解的思路是：由于航线是单向且保证了不可能通过一些道路和航线回到本身，所以说这个图由是很多个正边权无向边组成的联通块被一些可能有负权的有向边连接起来。

这样的话就可以把每个联通块视为一个点，可以按照拓扑序在每个联通块内跑Dijkstra最后求出答案。由于一些玄学的错误，这个代码我调了整整一天还没有调出来。最后草率的在SPFA上加了SFL优化A了这题。

代码

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#define MAXN 25005
#define MAXE 100005
#define INF 0x3f3f3f3f
using namespace std;

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

int t, r, p, s, a, b, c, cnt, head[MAXN], dis[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;
}

void spfa()
{
    deque<int> q;
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    vis[s]=true; dis[s]=0;
    q.push_back(s);
    while(!q.empty())
    {
        int x=q.front(); q.pop_front();
        vis[x]=false;
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(dis[to]>dis[x]+edge[i].dis)
            {
                dis[to]=dis[x]+edge[i].dis;
                if(vis[to]) continue;
                vis[to]=true;
                if(dis[to]<dis[q.front()]) q.push_front(to);
                else q.push_back(to);
            }
        }
    }
}

int main()
{
    scanf("%d%d%d%d", &t, &r, &p, &s);
    for(int i=1; i<=r; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        addedge(a, b, c);
        addedge(b, a, c);
    }
    for(int i=1; i<=p; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        addedge(a, b, c);
    }
    spfa();
    for(int i=1; i<=t; i++)
    {
        if(dis[i]==INF) printf("NO PATH\n");
        else printf("%d\n", dis[i]);
    }
}

Posted on Edited on In

问题描述

给你N个变量，M个不等式(形如x<y)，需要你判断：1.他们是否矛盾 2.若无矛盾，则是否能确定每个变量的关系 3.若能，则求出用前x个不等式就能求出关系x的最小值。

输入

有多组数据，每组数据第一行n,m。当n=0且m=0时输入结束。 下面m行给出m个不等式。

输出

对于每组数据输出下面三句话中的一句： Sorted sequence determined after xxx relations: yyy…y. Sorted sequence cannot be determined. Inconsistency found after xxx relations.

思路

求这些约束关系的当然是用拓扑排序啦。

拓扑排序时如果有两个或以上的点入度为0，则这个序列不能确定，如果没有一个入度为0的点，则这是矛盾的。然后每增加一个不等式时都进行一遍拓扑排序。

考虑输出，我们开一个数组记录这些变量，拓扑排序时按照拓扑序将这些变量加进数组，这样数组内的元素就一定时从大到小的。

细节

  1. 要注意输出格式
  2. 如果成功了，但以后的关系出现矛盾依然认为它成功
  3. 每一组数据要把输入读完

代码

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN 30
using namespace std;

int n, m, tag, top, pos, cnt, flag1, flag2, q[MAXN], deg[MAXN], temp[MAXN];
bool f[MAXN][MAXN];
char t[5];

int topo()
{
    top=0; flag2=1;
    for(int i=1; i<=n; i++) temp[i]=deg[i];
    for(int i=1; i<=n; i++)
    {
        cnt=0;
        for(int j=1; j<=n; j++)
            if(temp[j]==0) {cnt++; pos=j;}
        if(cnt==0) return 0;
        if(cnt>1) flag2=-1;
        q[top++]=pos;
        temp[pos]=-1;
        for(int j=1; j<=n; j++)
            if(f[pos][j]==1) temp[j]--;
    }
    return flag2;
}

int main()
{
    scanf("%d%d", &n, &m);
    while(n!=0 && m!=0)
    {
        memset(f, 0, sizeof(f));
        memset(deg, 0, sizeof(deg));
        flag1=false;
        for(int i=1; i<=m; i++)
        {
            scanf("%s", t);
            if(flag1) continue;
            int x=t[0]-'A'+1, y=t[2]-'A'+1;
            f[x][y]=true; deg[y]++;
            tag=topo();
            if(tag==0)
            {
                printf("Inconsistency found after %d relations.\n",i);
                flag1=1;
            }
            if(tag==1)
            {
                printf("Sorted sequence determined after %d relations: ",i);
                for(int j=0; j<n; j++) printf("%c", q[j]+'A'-1);
                printf(".\n");
                flag1=1;
            }
        }
        if(!flag1) printf("Sorted sequence cannot be determined.\n");
        scanf("%d%d", &n, &m);
    }
}

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);
}