图论-某图论专练 Round3 (April, 2018)

我实在太弱啦 OrzOrz ，B题负权回路没看出来，D题写爆，平时太懒练少了吧。

A. Floyd裸题， O(N^3) 。

B. Bellman-Ford 判负权回路，注意麦田间的小路是双向边，而虫洞是单向边，这是个巨大的坑点。

C. 贪心裸题，最少线段覆盖，也可以用图论做。

D. 二分答案 + 图论。二分一个最长电线长度，将大于这个长度的边权值置为 1 ，小于等于这个长度的边权置为 0，从

1 号点开始跑一遍最短路，Dis[N] 即为最少的需要电信公司免费搭建的电线数量。Dis[N] <= K 时，二分的答案是合理的。

 1 #include <stdio.h>
 2 
 3 const int INF = 1e9;
 4 
 5 int G[250][250], Dis[250];
 6 
 7 int main()
 8 {
 9     int N, M, Q, t1, t2, t3, i, j, k;
10     scanf("%d%d%d", &N, &M, &Q);
11     for (i = 1; i <= N; ++i) {
12         scanf("%d", &Dis[i]);
13         for (j = 1; j <= N; ++j)
14             G[i][j] = INF;
15         G[i][i] = 0;
16     }
17     for (i = 1; i <= M; ++i) {
18         scanf("%d%d%d", &t1, &t2, &t3);
19         if (t1 == t2) continue;
20         if (Dis[t1] >= t3) G[t1][t2] = 1;
21         if (Dis[t2] >= t3) G[t2][t1] = 1;
22     }
23     for (k = 1; k <= N; ++k)
24         for (i = 1; i <= N; ++i)
25             for (j = 1; j <= N; ++j)
26                 if (G[i][j] > G[i][k] + G[k][j])
27                     G[i][j] = G[i][k] + G[k][j];
28     while (Q--) {
29         scanf("%d%d", &t1, &t2);
30         if (G[t1][t2] == INF)
31             printf("no way
");
32         else
33             printf("%d
", G[t1][t2]);
34     }
35     return 0;
36 }

 1 #include <stdio.h>
 2 #include <vector>
 3 #include <queue>
 4 
 5 using namespace std;
 6 
 7 const int _N = 700;
 8 
 9 const int INF = 1e9;
10 
11 struct Node {
12     int v, w;
13     Node(int v, int w):
14         v(v), w(w) { }
15 };
16 
17 vector<Node> G[_N];
18 queue<int> Q;
19 int Dis[_N], N, GGG[_N][_N], book[_N], cnt[_N];
20 
21 inline void Ins(int t1, int t2, int t3) { G[t1].push_back(Node(t2, t3)); return; }
22 
23 bool Bellman(int Beg)
24 {
25     for (int i = 1; i <= N; ++i) Dis[i] = INF, book[i] = false, cnt[i] = 0;
26     while (!Q.empty()) Q.pop();
27     Dis[Beg] = 0, book[Beg] = true, Q.push(Beg), cnt[Beg] = 1;
28     while (!Q.empty()) {
29         int p = Q.front(); book[p] = false; Q.pop();
30         vector<Node>::iterator it;
31         for (it = G[p].begin(); it != G[p].end(); ++it)
32             if (Dis[it->v] > Dis[p] + it->w) {
33                 Dis[it->v] = Dis[p] + it->w;
34                 if (book[it->v]) continue;
35                 Q.push(it->v), book[it->v] = true;
36                 if (++cnt[it->v] == N+1) return true;
37                 if (it->v == Beg && Dis[it->v] < 0) return true;
38             }
39     }
40     return false;
41 }
42 
43 int main()
44 {
45     int T;
46     scanf("%d", &T);
47     while (T--) {
48         int t1, t2, t3, A, B, i, j;
49         scanf("%d%d%d", &N, &A, &B);
50         for (i = 1; i <= N; ++i) G[i].clear();
51         
52         for (i = 1; i <= N; ++i)
53             for (j = 1; j <= N; ++j)
54                 GGG[i][j] = INF;
55                 
56         while (A--) {
57             scanf("%d%d%d", &t1, &t2, &t3);
58             GGG[t1][t2] = min(GGG[t1][t2], t3);
59             GGG[t2][t1] = min(GGG[t2][t1], t3);
60         }
61         
62         while (B--) {
63             scanf("%d%d%d", &t1, &t2, &t3);
64             GGG[t1][t2] = min(GGG[t1][t2], -t3);
65         }
66         
67         for (i = 1; i <= N; ++i)
68             for (j = 1; j <= N; ++j)
69                 if (GGG[i][j] != INF)
70                     Ins(i, j, GGG[i][j]);
71         
72         if (Bellman(1))
73             printf("YES
");
74         else
75             printf("NO
");
76     }
77     return 0;
78 }

 1 #include <stdio.h>
 2 #include <vector>
 3 #include <queue>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 const int _N = 1100000;
 9 
10 typedef long long LL;
11 
12 const long long INF = 99999999999999LL;
13 
14 struct Node {
15     LL v, w;
16     Node(LL v, LL w):
17         v(v), w(w) { }
18 };
19 
20 struct StrDis {
21     LL v, dis;
22     StrDis(LL v, LL dis):
23         v(v), dis(dis) { }
24     bool operator < (const StrDis &tmp) const
25     {
26         return dis > tmp.dis;
27     }
28 };
29 
30 vector<Node> G[_N];
31 priority_queue<StrDis> Q;
32 LL Dis[_N], A[70000], A_cnt, N, T;
33 
34 void Dijkstra(LL Beg)
35 {
36     for (LL i = 1; i <= T+1; ++i) Dis[i] = INF;
37     while (!Q.empty()) Q.pop();
38     Dis[Beg] = 0;
39     Q.push(StrDis(Beg, Dis[Beg]));
40     while (!Q.empty()) {
41         StrDis p = Q.top(); Q.pop();
42         if (p.dis != Dis[p.v]) continue;
43         vector<Node>::iterator it;
44         for (it = G[p.v].begin(); it != G[p.v].end(); ++it)
45             if (Dis[it->v] > Dis[p.v] + it->w) {
46                 Dis[it->v] = Dis[p.v] + it->w;
47                 Q.push(StrDis(it->v, Dis[it->v]));
48             }
49     }
50     return;
51 }
52 
53 int main()
54 {
55     scanf("%lld%lld", &N, &T);
56     while (N--) {
57         LL t1, t2;
58         scanf("%lld%lld", &t1, &t2), ++t2;
59         if (t2 <= t1) continue;
60         A[++A_cnt] = t1, A[++A_cnt] = t2;
61         G[t1].push_back(Node(t2, 1));
62     }
63     sort(A+1, A+1+A_cnt);
64     for (LL i = 2; i <= A_cnt; ++i)
65         if (A[i] != A[i-1]) G[A[i]].push_back(Node(A[i-1], 0));
66     Dijkstra(1);
67     if (Dis[T+1] == INF)
68         printf("-1
");
69     else
70         printf("%lld
", Dis[T+1]);
71     return 0;
72 }

  1 #include <stdio.h>
  2 #include <vector>
  3 #include <queue>
  4 #include <algorithm>
  5 
  6 using namespace std;
  7 
  8 const int _N = 1200;
  9 const int _M = 12000;
 10 
 11 typedef long long LL;
 12 
 13 const long long INF = 99999999999999LL;
 14 
 15 struct Node {
 16     LL v, w;
 17     Node(LL v, LL w):
 18         v(v), w(w) { }
 19 };
 20 
 21 struct StrDis {
 22     LL v, dis;
 23     StrDis(LL v, LL dis):
 24         v(v), dis(dis) { }
 25     bool operator < (const StrDis &tmp) const
 26     {
 27         return dis > tmp.dis;
 28     }
 29 };
 30 
 31 vector<Node> G[_N];
 32 priority_queue<StrDis> Q;
 33 
 34 LL Dis[_N], Extra[_N], N, M, K, MaxLen;
 35 LL t1[_M], t2[_M], t3[_M];
 36 
 37 void diudiu_Dijkstra(LL Beg)
 38 {
 39     for (LL i = 1; i <= N; ++i) Dis[i] = INF;
 40     while (!Q.empty()) Q.pop();
 41     Dis[Beg] = 0;
 42     Q.push(StrDis(Beg, Dis[Beg]));
 43     while (!Q.empty()) {
 44         StrDis p = Q.top(); Q.pop();
 45         if (p.dis != Dis[p.v]) continue;
 46         vector<Node>::iterator it;
 47         for (it = G[p.v].begin(); it != G[p.v].end(); ++it)
 48             if (Dis[it->v] > Dis[p.v] + it->w) {
 49                 Dis[it->v] = Dis[p.v] + it->w;
 50                 Q.push(StrDis(it->v, Dis[it->v]));
 51             }
 52     }
 53     return;
 54 }
 55 
 56 inline void Ins(LL t1, LL t2, LL t3) { G[t1].push_back(Node(t2, t3)); G[t2].push_back(Node(t1, t3)); return; }
 57 
 58 bool Check(LL lim)
 59 {
 60     int i;
 61     for (i = 1; i <= N; ++i) G[i].clear();
 62     for (i = 1; i <= M; ++i) {
 63         if (t1[i] == t2[i]) continue;
 64         Ins(t1[i], t2[i], t3[i] > lim);
 65     }
 66     diudiu_Dijkstra(1);
 67     return Dis[N] <= K;
 68 }
 69 
 70 int main()
 71 {
 72     LL i;
 73     scanf("%lld%lld%lld", &N, &M, &K);
 74     for (i = 1; i <= M; ++i) {
 75         scanf("%lld%lld%lld", &t1[i], &t2[i], &t3[i]);
 76         if (t1[i] == t2[i]) continue;
 77         Ins(t1[i], t2[i], 1);
 78         MaxLen = max(MaxLen, t3[i]);
 79     }
 80     
 81     diudiu_Dijkstra(1);
 82     if (Dis[N] == INF) { printf("-1
"); return 0; }
 83     if (Dis[N] <= K) { printf("0
"); return 0; }
 84     
 85     for (i = 1; i <= N; ++i) G[i].clear();
 86     for (i = 1; i <= M; ++i) {
 87         if (t1[i] == t2[i]) continue;
 88         Ins(t1[i], t2[i], t3[i]);
 89     }
 90     
 91     LL l = 1, r = MaxLen;
 92     while (l <= r) {
 93         LL mid = l+r >> 1;
 94         if (Check(mid)) r = mid-1;
 95         else l = mid+1;
 96     }
 97     
 98     printf("%lld
", l);
 99     return 0;
100 }

题目：

A通讯靠吼
时间限制 : 10000 MS 空间限制 : 65536 KB
问题描述
亚马逊河流域部落的人们过着非常原始的生活，他们的通讯方式基本靠吼。何老板发现他们传消息的方式非常有意思，可以称为“吼叫传递”。比如A要传话给远处的D说"我稀饭你"，A会对着B大吼"我稀饭D"，接着B会对着C大吼"A稀饭D"，C又会对着D大吼"A稀饭你"。就这样，一个传一个，消息就传了出去。但是，如果两人之间有障碍阻隔(比如一座山、一片树林)消息就无法传递过去了。每个人的嗓音大小不同，所以喊话的声能够传递的距离也可能不同。
何老板今天访问的部落有n个原始人，何老板将它们编号1到n，白天，它们分布在雨林的各个地方进行劳作。何老板事先告诉你哪些人之间没有障碍物间隔，可以直接喊话。
假设每个人都不会移动位置。何老板提问说出两个人的编号x和y，你能否告诉他x要传话到y，最少几个人要吼？

输入格式
第一行，三个整数n,m,q。n表示共n个原始人，m表示有m对人之间无障碍阻隔，q表示何老板提问的个数。
第二行，n个空格间隔的整数，分别表示编号1到n的人每个人喊话声最远能传递的距离(<=5000)
接下来m行，每行三个整数x,y,z 表示编号x和编号y的人之间无障碍阻隔，他们的直线距离为z(<=5000)
接下来q行，每行两个整数x,y表示何老板想知道x传话到y最少需要几个人吼(x可能等于y)

输出格式
共q行，表示对何老板提问的回答。
对于每个提问，如果x能传话到y，输出一个整数，表示最少需要吼叫的人数。如果不能，输出"no way"

样例输入 1
6 9 3
9 10 7 8 6 3
1 2 8
2 3 9
1 5 7
5 2 16
4 3 3
3 6 8
5 6 6
4 6 5
1 4 5
1 3
6 2
2 6

样例输出 1
2
no way
3

样例输入 2
8 12 5
14 7 30 18 33 7 8 6
2 7 8
2 6 6
3 4 10
4 7 10
5 8 9
8 5 13
3 7 6
3 6 3
2 8 6
5 2 7
3 7 10
6 3 12
4 5
1 8
3 4
2 3
7 3

样例输出 2
3
no way
1
2
1

提示
n<=200 m<=10000 q<=1000

B虫洞
时间限制 : 10000 MS 空间限制 : 65536 KB
问题描述
农民约翰在巡查他的农场的时候发现了一些惊人的“虫洞”(“虫洞”的详情请参阅按因斯坦的解释)。虫洞非常奇特，它是一个单向通道，可以在瞬间把你传送到通道的另外一端，到达以后你会发现当前时间比你进洞时间要早(简单地说就是穿越了，回到了过去)。约翰的农场共有N块田，编号1到N，田与田之间共有M条小路相连(两块田间可能有多条小路相连)。约翰在这些田上总共找到了W个虫洞。
约翰是个穿越爱好者，他想做下面这些事：以某块田为起点出发，穿过一些小路和虫洞，然后回到起点，使他回到起点时的时间早于他出发的时间，也许这样他就能在起点上见到另一个他自己了。
为了帮助约翰知道他的方案能否可行，他会给你整个农场的地图。走过一条小路的耗时不会超过10000秒。一个虫洞一次最多能使时间倒退10000秒。

输入格式
第一行一个整数F，表示有F组测试数据。
对于每组测试数据：
第1行有三个整数N,M和W
接下来M行，每行三个空格间隔的整数S,E,T分别表示一条小路的起点，终点和通过所需时间。
接下来W行，每行三个空格间隔的整数S,E,T分别表示一个虫洞穿越的起点，终点和让时间倒退的秒数。

输出格式
包括F行，每行一个单词。"YES"表示约翰能成功。"NO"表示不能。

样例输入 1
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

样例输出 1
NO
YES

样例输入 2
5
5 10 2
1 3 277
3 5 7116
5 5 3567
2 4 6023
5 3 1453
3 1 1083
4 1 2414
1 3 8174
2 5 6055
3 2 9029
3 5 1466
2 5 88
5 10 2
2 4 8688
3 2 619
3 5 9103
5 5 6657
5 3 8188
3 3 7513
5 1 9068
1 3 5184
4 5 8318
4 3 3706
5 3 591
5 2 1605
5 10 2
4 3 7819
3 1 4797
4 3 6176
1 3 6207
2 1 9643
3 1 2436
2 5 2302
3 5 401
4 2 3435
2 2 4987
5 3 1173
3 4 1078
5 10 2
1 5 9720
5 2 7917
1 5 5038
2 4 6890
3 5 9688
1 5 1063
1 3 5468
5 2 5244
2 2 435
1 5 5763
5 4 293
1 2 929
5 10 2
4 3 66
4 4 8651
3 4 8304
4 5 7845
2 3 2923
1 3 5425
1 1 526
5 4 2853
1 3 4244
5 3 6174
2 5 1090
1 4 103

样例输出 2
YES
NO
YES
NO
NO

提示
【数据范围】
1<=N<=500
1<=M<=2500
1<=W<=200
1<=F<=5

C刷题
时间限制 : - MS 空间限制 : 165536 KB
评测说明 : 2s
问题描述
寒假里，何老板安排信竞班的N名学生去NKOJ刷题。
寒假总共有T分钟，何老板要求每一分钟都至少有一个同学在刷题。这样的要求，让同学们很是恼火。
每个学生只愿抽出一段特定时间刷题，比如第i个学生只愿意在[Si,Ei]这个时间段刷题。
假期里大家都想玩，于是同学们想计算出最少需要安排多少个同学刷题就能满足要求。如果无解输出-1.

输入格式
第1行：两个整数N和T．

接下来N行，每行两个整数表示一个学生刷题的时间段[Si，Ei]

输出格式
最少安排刷题的学生数．

样例输入 1
3 10
1 7
3 6
6 10

样例输出 1
2

样例输入 2
3 10
1 3
4 7
8 10

样例输出 2
3

样例输入 3
7 1000000
1 100000
99999 100001
100000 200000
200000 500000
210000 490000
499992 799987
799988 1000000

样例输出 3
5

提示
1≤T≤1000000
1≤N≤25000
1≤Si≤Ei≤T
样例1说明
假期总共10分钟，安排学生1和学生3参与刷题即可保证每分钟都至少有一个同学在刷题．

D架电话线
时间限制 : 10000 MS 空间限制 : 65536 KB
问题描述
Farmer John打算将电话线引到自己的农场，但电信公司并不打算为他提供免费服务。于是，FJ必须为此向电信公司支付一定的费用。
FJ的农场周围分布着N根按1..N顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P对电话线杆间可以拉电话线，其余的那些由于隔得太远而无法被连接。
第i对电话线杆的两个端点分别为A_i、B_i，它们间的距离为L_i 。数据中保证每对{A_i，B_i}最多只出现1次。编号为1的电话线杆已经接入了全国的电话网络，整个农场的电话线全都连到了编号为N的电话线杆上。也就是说，FJ的任务仅仅是找一条将1号和N号电话线杆连起来的路径，其余的电话线杆并不一定要连入电话网络。
经过谈判，电信公司最终同意免费为FJ连结K对由FJ指定的电话线杆。对于此外的那些电话线，FJ需要为它们付的费用，等于其中最长的电话线的长度（每根电话线仅连结一对电话线杆）。如果需要连结的电话线杆不超过K对，那么FJ的总支出为0。
请你计算一下，FJ最少需要在电话线上花多少钱。

输入格式
第一行输入3个用空格隔开的整数：N、P、以及K
以下P行中，第i行为3个用空格隔开的整数：A_i、B_i、L_i。

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

样例输入 1
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

样例输出 1
4

样例输入 2
4 5 0
1 4 8
2 4 2
2 1 5
3 1 9
3 2 9

样例输出 2
5

样例输入 3
8 20 3
3 6 14
2 4 12
6 5 15
7 8 9
2 6 9
3 5 6
2 1 14
6 4 1
5 8 2
4 5 13
8 6 5
7 5 1
4 8 2
7 3 10
6 7 1
7 4 10
2 8 9
7 1 13
5 1 6
5 2 3

样例输出 3
0

提示
(1<=N<=1,000)
(1<=P<=10,000)
(1<=L_i<=1,000,000)
(0<=K<N)

样例1说明
FJ选择如下的连结方案：1->3、3->2、2->5，这3对电话线杆间需要的电话线的长度分别为4、3、9。FJ让电信公司提供那条长度为9的电话线，于是，他所需要购买的电话线的最大长度为4。