Dylan's Blog
0%

Posted on Edited on In

问题描述

大意就是给你一个无向图，求出它的最小环。 并输出最小环上的点。（会有SPJ）

输出

第一行n(n<=100), m(m<=10000)。表示有n个点，m条边。 接下来m行，每一行描述一条边。

输出

输出最小环上的所有节点

思路

求最小环是用Floyd的方法。

我们按顺序枚举所有点，再枚举与该点相邻的点对。枚举点对时，我们可以不需要考虑编号比该点大的点，因为编号比它大的点在后面会被枚举到，会包含这种情况。环的长度就是该点到点对的距离与点对之间的距离之和。

接下来考虑输出环上的点。记录路径感觉很难，于是膜了一下书上的做法。每进行一次松弛操作时就记录一下。环上的点就是点对之间的最短路径上的点和该点对。可以递归下去找最短路径上的点，有点像记录DP方案。(似乎有点难讲清楚，代码还是比较好懂的)。

细节

  1. 小心有重边。
  2. 枚举完点对之后不要忘记Floyd更新点之间的距离
  3. 更新ans时一点要开longlong (代码38行)
  4. 记录路径时递归不要弄错了
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 <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#define MAXN 105
#define INF 0x3f3f3f3f
using namespace std;

int n, m, x, y, z, ans=INF, mmp[MAXN][MAXN], dis[MAXN][MAXN], f[MAXN][MAXN];
vector<int> path;

void find(int i, int j)
{
    if(!f[i][j]) return;
    find(i, f[i][j]);
    path.push_back(f[i][j]);
    find(f[i][j], j);
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(mmp, 0x3f, sizeof(mmp));
    memset(dis, 0x3f, sizeof(dis));
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d", &x, &y, &z);
        if(mmp[x][y]<z) continue;
        mmp[x][y]=mmp[y][x]=z;
        dis[x][y]=dis[y][x]=z;
    }
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<k; i++)
            for(int j=i+1; j<k; j++)
            {
                if(ans>(long long)dis[i][j]+mmp[i][k]+mmp[k][j])
                {
                    path.clear();
                    path.push_back(i);
                    find(i, j);
                    path.push_back(j);
                    path.push_back(k);
                    ans=dis[i][j]+mmp[i][k]+mmp[k][j];
                }
            }
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
            {
                if(dis[i][j]>dis[i][k]+dis[k][j])
                {
                    dis[i][j]=dis[i][k]+dis[k][j];
                    f[i][j]=k;
                }
            }
    }
    if(ans==INF) printf("No solution.");
    else for(int i=0; i<path.size(); i++) printf("%d ", path[i]);
}

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