省赛前的刷题训练(四)

发表于 更新于 分类于 阅读次数：

省赛刷题训练（四）

Highway Project

ZOJ 3946

最短路问题,需要在最短时间的最基础求另一个最小花费，实际上只需要在if(dist[] > dist[] + w)中加上另外判断的两句即可。还有需要注意的是，dist[]数组要开Long long ，最后求总的花费的时候，不要把0点加进去，除非你已经设定dist[0] = 0 且 cost[0] = 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
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
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <queue>
#include <string>
using namespace std;
const int maxn = 200001;
const int inf = 0x3f3f3f3f;
struct node{
    int v,t,m,next;
}edge[300001];
int tot, N, M;
int vis[maxn],head[maxn],cost[maxn];
long long dist[maxn];
int add(int u,int v,int time,int money)
{
    edge[tot].v = v;
    edge[tot].t = time;
    edge[tot].m = money;
    edge[tot].next = head[u];
    head[u] = tot++;
}
int spfa(int s)
{
    dist[s] = 0;
    vis[s] = 1;
    queue<int>Q;
    Q.push(s);
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        vis[u] = 0;
        for(int k = head[u] ; k != -1; k = edge[k].next)
        {
            int v = edge[k].v;
            int t = edge[k].t;
            int m = edge[k].m;
            if(dist[v] > dist[u] +  t || (dist[v] == dist[u] + t && cost[v] > m))
            {
                dist[v] = dist[u] + t;
                cost[v] = m;
                if(!vis[v])
                {
                    vis[v] = 1;
                    Q.push(v);
                }
            }
        }
    }
}
int main()
{
    int T, u ,v, t ,m;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&N,&M);
        memset(vis,0,sizeof(vis));
        memset(dist,inf,sizeof(dist));
        memset(head,-1,sizeof(head));
        memset(cost,inf,sizeof(cost));
        tot = 1;
        for(int i = 1; i <= M; ++i)
        {
            scanf("%d %d %d %d", &u,&v,&t,&m);
            add(u,v,t,m);
            add(v,u,t,m);
        }
        spfa(0);
        long long sum = 0;
        long long sum1 = 0;
        for(int i = 1; i < N; ++ i)
        {
            sum1 += dist[i];
            sum += cost[i];
        }
        cout << sum1 << ' ' << sum << '\n';
    }
}

Rank of Tetris

HDU 1811

相等的时候需要用并查集进行合并，我做的时候，遇到 > 就加边， 遇到<就加边，遇到等号就合并，问题是合并了之后并不会对以前的结果有影响，因此第一次输入的时候我只是先处理等号的情况，其他的情况先存起来，先把=的对象合并起来。第二次再处理 >和< ,但是我们在进行加边的时候，需要先查找两个对象的祖先，再进行加边，这样也就意味着我们把所有是=的对象看成一个团体了，我WA了好几次，都是f[i]和 Find(i)傻傻分不清，还要注意在进行拓扑排序的时候，一开始我们往里push的时候，不仅要求in[i] == 0 还必须满足 Find(i) == i，否则对于那些我们已经不管的是等于号的节点也加进去了。感觉这道题还是很不错了，以后有时间还要再做一遍。

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
112
113
114
115
116
117
118
119
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 20001;
struct node{
  int A, B;
  string s;
}a[20001];
vector<int>G[maxn];
int flag , sum, f[20001], n, m, in[30001],cnt;
int Find(int x)
{
    if(x != f[x])
    {
        f[x] = Find(f[x]);
    }
    return f[x];
}
int combine(int a,int b)
{
    int fa = Find(a);
    int fb = Find(b);
    if(fa != fb)
    {
        f[fa] = fb;
    }
}
int bfs()
{
    queue<int>Q;
    for(int i = 0; i < n; ++i)
    {
        if(!in[i] && Find(i) == i)
        {
            Q.push(i);
        }
    }
    while(!Q.empty())
    {
        if(Q.size() > 1)
        {
            flag = 0;
        }
        int u = Q.front();
        Q.pop();
        cnt++;
        for(int i = 0; i < G[u].size(); ++i)
        {
            int v = G[u][i];
            in[v]--;
            if(!in[v])
            {
                Q.push(v);
            }
        }
    }
    if(cnt != sum)
        flag = 2;
}
int main()
{
    int  A, B;
    while(cin >> n >> m){
    sum = n;
    cnt = 0;
    flag = 1;
    for(int i = 0; i < n; ++i)
    {
        G[i].clear();
    }
    memset(in,0,sizeof(in));
    for(int i = 0; i < n; ++i)
        f[i] = i;
    for(int i = 1; i <= m; ++i)
    {
        string s;
        cin >> a[i].A >> a[i].s >> a[i].B;
        if(a[i].s[0] == '=')
        {
            if(Find(a[i].A) != Find(a[i].B))
            {
                combine(a[i].A , a[i].B);
                sum--;
            }
        }
    }
    for(int i = 1; i <= m; ++i)
    {
        if(a[i].s[0] == '>')
        {
            A = Find(a[i].A);
            B = Find(a[i].B);
            G[A].push_back(B);
            in[B] ++;
        }
        else if(a[i].s[0] == '<')
        {
            A = Find(a[i].A);
            B = Find(a[i].B);
            G[B].push_back(A);
            in[A]++;
        }
        else{
              continue;
        }
    }
    bfs();
    if(flag == 2)
        cout << "CONFLICT" << '\n';
    else if(flag == 0)
        cout << "UNCERTAIN" << '\n';
    else
        cout << "OK" << '\n';
    }
}