分类目录归档:图论

洛谷 P1113 杂务

这题本来就是个拓扑排序,搞了半天竟然搞不出来,想了半天。。
一开始的想法是:搞拓扑排序,一轮一轮的扫描,每一轮出一个最大时间,把最大时间相加就好了,后来发现全WA,为什么呢?因为同一轮里出来的任务其实有可能是不互相依赖的。比如任务1时间需要10;任务2时间需要5;任务3需要在任务1之后,任务4需要在任务2之后。如果一轮一轮的扫描,那么必须10秒之后同时开始做任务3/4。而实际情况则应该是任务2,5个时间作完之后就可以做任务4了。根据失误我又想着反向建图,用DFS递归解决,对每个结点(及其之前节点)找其最大的所用时间,写出来AC了(对于本题,杂务 k(k>1)的准备工作只可能在杂务 1 至 k-1 中,如果没有这个要求,反向建图就很好)。但是其实我想多了。直接一开始的拓扑排序,顺着推就可以了。
DFS版:

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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,times[10005],inDegree[10005],f[10005];
vector<int> edges[10005];
vector<int> curTasks;
int dfs(int node){
    if(f[node]!=0)return f[node];
    if(edges[node].size()==0)return f[node]=times[node];
    int maxT=0;
    for(int i=0;i<edges[node].size();i++){
        maxT=max(maxT,dfs(edges[node][i]));
    }
    return f[node]=maxT+times[node];
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        int v;
        cin>>v>>times[i];
        while(1){
            cin>>v;
            if(v==0)break;
            edges[i].push_back(v);
            inDegree[v]++;
        }
    }
    int maxTime=0;
    for(int i=1;i<=n;i++){
        if(inDegree[i]==0)maxTime=max(maxTime,dfs(i));
    }
    cout<<maxTime;
}

正常版:

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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,times[10005],inDegree[10005],allTimes[10005];
vector<int> edges[10005];
int sumTime=0;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        int v;
        cin>>v>>times[i];
        while(1){
            cin>>v;
            if(v==0)break;
            edges[v].push_back(i);
            inDegree[i]++;
        }
    }
    int maxT=0;
    for(int i=1;i<=n;i++)if(inDegree[i]==0){
        allTimes[i]+=times[i];
        for(int j=0;j<edges[i].size();j++){
            allTimes[edges[i][j]]=max(allTimes[edges[i][j]],allTimes[i]);
            inDegree[edges[i][j]]--;
        }
        inDegree[i]--;
        maxT=max(maxT,allTimes[i]);
    }
    cout<<maxT;
}

洛谷 P1144 最短路计数

自己一开始写了个,才60分,效率不高,后来看了题解。
参考题解:https://www.luogu.org/blog/user43513/luo-gu-p1144-zui-duan-lu-ji-shuo-ti-xie
60分代码:

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<iostream>
#include<cstring>
#include<queue>
#define MAXN 1000000
#define MAXM 2000000
#define MOD 100003
using namespace std;
int n,m;
int v[MAXM+5],nxt[MAXM+5];
bool visited[MAXM+5];
int fst[MAXN+5];
int dis[MAXN+5];
int cnter[MAXN+5];
int edgePtr=0;
void edgePush(int s,int e){
    edgePtr++;
    nxt[edgePtr]=fst[s];
    v[edgePtr]=e;
    fst[s]=edgePtr;
}
void SP(){
    memset(visited,false,sizeof(visited));
    memset(dis,0x7f,sizeof(dis));
    queue<int> q,qd;
    q.push(1);qd.push(0);
    while(!q.empty()){
        int node=q.front(),dist=qd.front();
        q.pop();qd.pop();
        if(visited[node])continue;
        visited[node]=true;
        dis[node]=dist;
        for(int e=fst[node];e!=-1;e=nxt[e]){
            if(!visited[v[e]]&&dis[v[e]]>dis[node]+1){
                dis[v[e]]=dis[node]+1;
                q.push(v[e]);qd.push(dis[v[e]]);
            }
        }
    }
}
void DFS(int node,int dist){
    if(dist!=dis[node])return;
    cnter[node]++;
    cnter[node]%=MOD;
    for(int e=fst[node];e!=-1;e=nxt[e]){
        if(visited[e])continue;
        visited[e]=true;
        DFS(v[e],dist+1);
        visited[e]=false;
    }
}
int main(){
    memset(fst,-1,sizeof(fst));
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        if(x==y)continue;
        edgePush(x,y);
        edgePush(y,x);
    }
    SP();
    memset(visited,false,sizeof(visited));
    DFS(1,0);
    for(int i=1;i<=n;i++)cout<<cnter[i]<<endl;
}

100分的:

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
#include<iostream>
#include<cstring>
#include<queue>
#define MAXN 1000000
#define MAXM 2000000
#define MOD 100003
using namespace std;
int n,m;
int v[MAXM+5],nxt[MAXM+5];
bool visited[MAXM+5];
int fst[MAXN+5];
int dis[MAXN+5];
int cnter[MAXN+5];
int edgePtr=0;
void edgePush(int s,int e){
    edgePtr++;
    nxt[edgePtr]=fst[s];
    v[edgePtr]=e;
    fst[s]=edgePtr;
}
void SP(){
    memset(visited,false,sizeof(visited));
    memset(dis,0x7f,sizeof(dis));
    queue<int> q,qd;
    q.push(1);qd.push(0);
    cnter[1]=1;
    while(!q.empty()){
        int node=q.front(),dist=qd.front();
        q.pop();qd.pop();
        if(visited[node])continue;
        visited[node]=true;
        dis[node]=dist;
        for(int e=fst[node];e!=-1;e=nxt[e]){
            if(!visited[v[e]]&&dis[v[e]]>dis[node]+1){
                dis[v[e]]=dis[node]+1;
                q.push(v[e]);qd.push(dis[v[e]]);
                cnter[v[e]]+=cnter[node];
                cnter[v[e]]%=MOD;
            }else if(dis[v[e]]==dis[node]+1){
                cnter[v[e]]+=cnter[node];
                cnter[v[e]]%=MOD;
            }
        }
    }
}
int main(){
    memset(fst,-1,sizeof(fst));
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        if(x==y)continue;
        edgePush(x,y);
        edgePush(y,x);
    }
    SP();
    for(int i=1;i<=n;i++)cout<<cnter[i]<<endl;
}

洛谷 P1346 电车

基本上是裸的最短路,是第一个不用扳道岔的边长就是0,后面的需要扳道岔的长度就是1。然后愉快的套一个Dijkstra板子就可以了。

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
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int n,a,b;
struct edge{
    int v,w;
    edge(int vv,int ww){v=vv;w=ww;}
    bool operator < (const edge& e2) const{
        return w>e2.w;
    }
};
vector<edge> edges[105];
priority_queue<edge> pq;
bool visited[105];
int dis[105];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        for(int j=1;j<=t;j++){
            int v;
            cin>>v;
            if(j==1)edges[i].push_back(edge(v,0));
            else edges[i].push_back(edge(v,1));
        }
    }
    //Dijkstra
    memset(dis,0x7f,sizeof(dis));
    pq.push(edge(a,0));
    while(!pq.empty()){
        edge cur=pq.top();
        pq.pop();
        if(visited[cur.v])continue;
        visited[cur.v]=true;
        dis[cur.v]=cur.w;
        for(int i=0;i<edges[cur.v].size();i++){
            if(!visited[edges[cur.v][i].v]&&dis[edges[cur.v][i].v]>dis[cur.v]+edges[cur.v][i].w){
                dis[edges[cur.v][i].v]=dis[cur.v]+edges[cur.v][i].w;
                pq.push(edge(edges[cur.v][i].v,dis[edges[cur.v][i].v]));
            }
        }
    }
    if(dis[b]!=0x7f7f7f7f)cout<<dis[b];
    else cout<<-1;
}

洛谷 P1991 无线通讯网

这道题很显然能够看出,只需找出与卫星电话数相等的联通块数,然后取联通块里的最大边就可以了。但是我想不出来怎么好写。
看过题解之后,经题解提醒“树的性质:删掉n条边一定出现n+1个连通块”,这样就好做了。

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
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int s, p;
struct edge {
    int u, v;
    double w;
    bool operator < (const edge& e2) const {
        return w < e2.w;
    }
}edges[125000];
struct point {
    int x, y;
}points[505];
int father[505];
int _find(int x) {
    if (father[x] == 0)return x;
    return father[x] = _find(father[x]);
}
bool _union(int x, int y) {
    x = _find(x); y = _find(y);
    if (x == y)return false;
    father[x] = y;
    return true;
}
inline double dis(int x1, int y1, int x2, int y2) {
    return sqrt((double)((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2)));
}
int main() {
    //ios::sync_with_stdio(false);
    cin >> s >> p;
    for (int i = 1; i <= p; i++) {
        cin >> points[i].x >> points[i].y;
    }
    int ePtr = 0;
    for (int i = 1; i <= p; i++) {
        for (int j = i + 1; j <= p; j++) {
            ePtr++;
            edges[ePtr].u = i;
            edges[ePtr].v = j;
            edges[ePtr].w = dis(points[i].x, points[i].y, points[j].x, points[j].y);
        }
    }
    sort(edges + 1, edges + ePtr + 1);
    int cnter = 0;
    for (int i = 1; i <= ePtr; i++) {
        if (_union(edges[i].u, edges[i].v)) {
            cnter++;
        }
        if (cnter == p - 1 - (s - 1)) {
            printf("%.2lf", edges[i].w);
            break;
        }
    }
}

洛谷 P4779 【模板】单源最短路径(标准版)

SPFA 40;Dijkstra AC.
这个Dijkstra是没问题的版本,有问题的参见:https://renjikai.com/luogu-p1339/

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int t, c, ts;
struct edge {
    long long v, w;
    edge(int vv, int ww) { v = vv; w = ww; }
    bool operator < (const edge& e2) const{
        return w > e2.w;
    }
};
vector<edge> edges[100005];
long long dis[100005];
bool inqueue[100005];
bool visited[100005];
void SPFA() {
    queue<int> q;
    dis[ts] = 0;
    inqueue[ts] = true;
    q.push(ts);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        inqueue[node] = false;
        for (int i = 0; i < edges[node].size(); i++) {
            if (dis[edges[node][i].v] > dis[node] + edges[node][i].w) {
                dis[edges[node][i].v] = dis[node] + edges[node][i].w;
                if (!inqueue[edges[node][i].v])q.push(edges[node][i].v);
            }
        }
    }
}
void dijkstra() {
    priority_queue<edge> pq;
    pq.push(edge(ts,0));
    while (!pq.empty()) {
        edge e = pq.top();
        pq.pop();
        if (visited[e.v])continue;
        visited[e.v] = true;
        dis[e.v] = e.w;
        for (int i = 0; i < edges[e.v].size(); i++) {
            if (!visited[edges[e.v][i].v] && dis[edges[e.v][i].v] > dis[e.v] + edges[e.v][i].w) {
                //有可能存在一种情况:虽然没有轮到点i成为离已处理完毕的点集最近的点,但点i的距离值已经由其它处理中或处理完毕的点多次更新,所以松弛的第二个条件必须加入
                dis[edges[e.v][i].v] = dis[e.v] + edges[e.v][i].w;
                pq.push(edge(edges[e.v][i].v, dis[edges[e.v][i].v]));
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin >> t >> c >> ts;
    for (int i = 1; i <= c; i++) {
        int rs, re, ci;
        cin >> rs >> re >> ci;
        edges[rs].push_back(edge(re, ci));
    }
    memset(dis, 0x7f, sizeof(dis));
    //SPFA();
    dijkstra();
    for(int i=1;i<=t;i++)cout << dis[i]<<" ";
}

洛谷 P1339 [USACO09OCT]热浪Heat Wave

头一次用dijkstra写题也是想试验一下,priority_queue的小根堆用的不熟。。让人不知所以。。。
应该有个这样的小窍门。pq的默认是搞大根堆的,直接想非常不好想,写排序规则的地方只写<号,然后写成“假设你就要把大数排在前面,即顺着pq排序规则走的规则,然后把符号一反即可”。 两种方法代码里都有: 注意!该题中的Dijkstra算法错误,请勿继续使用!错误问题在堆判断dis时不能做到实时动态更新,而将dis插入到堆排序的结构体中可以使得堆中重复插入点相同,路径值不同的结构体值,这样点同路径值小的可以传到堆顶,大的在到顶时被忽略。
没问题的版本参见:https://renjikai.com/luogu-p4779/

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int t, c, ts, te;
struct edge {
    int v, w;
    edge(int vv, int ww) { v = vv; w = ww; }
};
vector<edge> edges[2505];
int dis[2505];
bool inqueue[2505];
//bool visited[2505];
/*
struct cmp {
    bool operator () (int i1, int i2) {
        return dis[i1] > dis[i2];
    }
};
*/

void SPFA() {
    queue<int> q;
    dis[ts] = 0;
    inqueue[ts] = true;
    q.push(ts);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        inqueue[node] = false;
        for (int i = 0; i < edges[node].size(); i++) {
            if (dis[edges[node][i].v] > dis[node] + edges[node][i].w) {
                dis[edges[node][i].v] = dis[node] + edges[node][i].w;
                if (!inqueue[edges[node][i].v])q.push(edges[node][i].v);
            }
        }
    }
}
/*
void dijkstra() {
    priority_queue<int,vector<int>,cmp> pq;
    dis[ts] = 0;
    pq.push(ts);
    while (!pq.empty()) {
        int node = pq.top();
        pq.pop();
        if (visited[node])continue;
        visited[node] = true;
        for (int i = 0; i < edges[node].size(); i++) {
            if (!visited[edges[node][i].v] && dis[edges[node][i].v] > dis[node] + edges[node][i].w) {
                //有可能存在一种情况:虽然没有轮到点i成为离已处理完毕的点集最近的点,但点i的距离值已经由其它处理中或处理完毕的点多次更新,所以松弛的第二个条件必须加入,这也是为什么cmp必须要用实时的数据
                dis[edges[node][i].v] = dis[node] + edges[node][i].w;
                pq.push(edges[node][i].v);
            }
        }
    }
}
*/

int main() {
    ios::sync_with_stdio(false);
    cin >> t >> c >> ts >> te;
    for (int i = 1; i <= c; i++) {
        int rs, re, ci;
        cin >> rs >> re >> ci;
        edges[rs].push_back(edge(re, ci));
        edges[re].push_back(edge(rs, ci));
    }
    memset(dis, 0x7f, sizeof(dis));
    SPFA();
    //dijkstra();
    cout << dis[te];
}

洛谷 P1341 无序字母对

本题涉及欧拉回路/欧拉路径。
参考:https://blog.csdn.net/qq_34454069/article/details/77779300
http://www.cnblogs.com/zmin/p/6947266.html
https://www.cnblogs.com/shao0099876/p/7366852.html

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<vector>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
struct e {
    char t;
    int bool_v;
    e(char t1, int v1) { t = t1; bool_v = v1; }
    bool operator < (const e& e2) const {
        return t < e2.t;
    }
};
vector<e> edge[130];
vector<char> path;
int degree[130];
bool visited[3000];
void dfs(char node) {
    for (int i = 0; i < edge[node].size(); i++) {
        if (visited[edge[node][i].bool_v])continue;
        visited[edge[node][i].bool_v] = true;
        dfs(edge[node][i].t);
    }
    path.push_back(node);
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        char c1, c2;
        cin >> c1 >> c2;
        degree[c1]++;
        degree[c2]++;
        edge[c1].push_back(e(c2, i));
        edge[c2].push_back(e(c1, i));
    }
    for (char i = 0; i <= 126; i++) {
        if (edge[i].size() > 1)sort(edge[i].begin(), edge[i].end());
    }
    int odd = 0;//奇
    char s = -1;
    for (char i = 127; i >= 0; i--) {
        if (degree[i] % 2 == 0 && degree[i] > 0) {
            if (odd == 0)s = i;
        }
        else if (degree[i] % 2 == 1) {
            odd++;
            s = i;
        }
    }
    if (!(odd == 0 || odd == 2)) {
        cout << "No Solution";
        return 0;
    }
    dfs(s);
    for (int i = path.size() - 1; i >= 0; i--) {
        cout << path[i];
    }
}

可能确实不大好理解这个代码,然后就做了一个简易的例子来说明这个问题。

洛谷 P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm

今后需要改良一下拓扑排序,不要一遍一遍扫。只要抓到一个入度为0的就紧追不舍即可,一遍一遍的扫很耗费时间的。。。具体可看代码。

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
#include<iostream>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int nxt[100005];
bool visited[100005];
int allocated[100005];
int alloc_ptr = 0;
int allocate_dis[100005];
int chainDis[100005];
int inDegree[100005];
inline void removeInDegree(int node) {
    if (inDegree[node] != 0)return;
    inDegree[node]--;
    inDegree[nxt[node]]--;
    removeInDegree(nxt[node]);
}
inline int dfsRing(int alloc, int node) {
    if (visited[node])return 0;
    visited[node] = true;
    allocated[node] = alloc;
    return 1 + dfsRing(alloc, nxt[node]);
}
inline int dfsToRing(int node) {
    if (chainDis[node] != 0)return chainDis[node];
    if (allocated[node])return chainDis[node] = allocate_dis[allocated[node]];
    else return chainDis[node] = 1 + dfsToRing(nxt[node]);
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> nxt[i];
        inDegree[nxt[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0)removeInDegree(i);
    }
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] <= 0 || allocated[i]) continue;
        alloc_ptr++;
        allocate_dis[alloc_ptr] = dfsRing(alloc_ptr, i);
    }
    for (int i = 1; i <= n; i++) {
        if (allocated[i])cout << allocate_dis[allocated[i]] << endl;
        else cout << dfsToRing(i) << endl;
    }
}

洛谷 P2661 信息传递

小小的激动一下,自己做出来的。。
然后有个警醒,如果不是顺其自然简化的条件判断表达式(例如!flag,是flag==0的同义),不要生搬硬套简化,很容易出错!

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
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int To[200005];
int inDegree[200005];
int getRing(int node) {
    if (!inDegree[node])return 0;
    inDegree[node] = 0;
    return 1 + getRing(To[node]);
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> To[i];
        inDegree[To[i]]++;
    }
    int flag = 0;
    do {
        flag = 0;
        for (int i = 1; i <= n; i++) {
            if (inDegree[i]==0) {
                inDegree[i]--;
                inDegree[To[i]]--;
                flag++;
            }
        }
    } while (flag!=0);
    int mmin = 0x7fffffff;
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] > 0)mmin = min(mmin, getRing(i));
    }
    cout << mmin;
}

洛谷 车站分级

题号:P1983
算法标签:拓扑排序
洛谷题解地址:https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1983
参考题解:作者: chenshaoqian 更新时间: 2016-09-25 21:08
作者: mangoyang 更新时间: 2016-09-24 17:20

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<list>
#include<stack>
using namespace std;
#define virtual_point_start 1000
int n, m;
int s[1005];
int virtual_point_ptr = virtual_point_start;
int indegree[3000];
int pass[1005][1005];
int path_dis[3000];
list<int> edge[3000];
vector<int> t_edge_to;
stack<int> cur_level;
bool execute(){
    while (!cur_level.empty())cur_level.pop();
    for (int i = 1; i <= n; i++){
        if (indegree[i] == 0){
            cur_level.push(i);
            indegree[i] = -1;
        }
    }
    for (int i = 1001; i <= virtual_point_ptr; i++){
        if (indegree[i] == 0){
            cur_level.push(i);
            indegree[i] = -1;
        }
    }
    if (cur_level.empty())return false;
    while (!cur_level.empty()){
        int cur = cur_level.top();
        cur_level.pop();
        for (list<int>::iterator iter = edge[cur].begin(); iter != edge[cur].end(); iter++){
            indegree[*iter]--;
            int point_dis = (cur <= 1000);
            path_dis[*iter] = max(path_dis[*iter],path_dis[cur] + point_dis);
        }
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++)cin >> pass[i][j];
        t_edge_to.clear();
        int ptr = 1;
        for (int j = pass[i][1]; j <= pass[i][s[i]]; j++){
            if (pass[i][ptr] == j)ptr++;
            else t_edge_to.push_back(j);
        }
        virtual_point_ptr++;
        for (vector<int>::iterator iter = t_edge_to.begin(); iter != t_edge_to.end(); iter++){
            edge[virtual_point_ptr].push_back(*iter);
            indegree[*iter]++;
        }
        for (int se = 1; se <= s[i]; se++){
            edge[pass[i][se]].push_back(virtual_point_ptr);
            indegree[virtual_point_ptr]++;
        }
    }
    while (execute());
    int ans = 0;
    for (int i = 1; i <= n; i++){
        ans = max(ans, path_dis[i]);
    }
    cout << ans+1;
}

20180814更新:
题解:https://www.luogu.org/blog/24212/solution-p1983
主要是借鉴了一个开一个二维数组判断边是否加重的问题。
还有一个最重要的就是“由停车的站向不停车的站连边”问题,总是考虑不到。

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
#include<iostream>
#include<vector>
using namespace std;
int n,m;
bool visited[1002][1002];
int inDegree[1002],grades[1002];
vector<int> edges[1002];
vector<int> railStation;
vector<int> unStopStation;
vector<int> curGrade;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        railStation.clear();
        unStopStation.clear();
        int num;
        cin>>num;
        for(int j=1;j<=num;j++){
            int t;
            cin>>t;
            railStation.push_back(t);
        }
        for(int j=0;j<railStation.size()-1;j++){
            for(int k=railStation[j]+1;k<railStation[j+1];k++){
                unStopStation.push_back(k);
            }
        }
        for(int j=0;j<railStation.size();j++){
            for(int k=0;k<unStopStation.size();k++){
                if(visited[railStation[j]][unStopStation[k]])continue;
                visited[railStation[j]][unStopStation[k]]=true;
                edges[railStation[j]].push_back(unStopStation[k]);
                inDegree[unStopStation[k]]++;
            }
        }
    }
    int maxV=0;
    do{
        curGrade.clear();
        for(int i=1;i<=n;i++){
            if(inDegree[i]==0){
                curGrade.push_back(i);
                inDegree[i]--;
            }
        }
        for(int i=0;i<curGrade.size();i++){
            grades[curGrade[i]]++;
            for(int j=0;j<edges[curGrade[i]].size();j++){
                grades[edges[curGrade[i]][j]]=max(grades[edges[curGrade[i]][j]],grades[curGrade[i]]);
                inDegree[edges[curGrade[i]][j]]--;
            }
            maxV=max(maxV,grades[curGrade[i]]);
        }
    }while(curGrade.size());
    cout<<maxV;
}